0

I am researching the maximum subarray problem. It would appear that I haven't gotten the core idea. Let's say you have the following array: int arr[] ={10, 4, 2, 12, 16, 1} From what I understand the maximum subarray should be equal to 14, since the lowest and highest possible sub array is 2 (the third element) and 16 (the 5th element) right? Well, apperantly not. I implemented the linear time algorithm which I found here: http://heliang.me/wiki/index.php?title=4.1_The_maximum-subarray_problem It's implementation in c++"

int max_sarr(int arr[], int size)
{
    int  max_sum = -9999;
    int sum = 0;
    for(int i = 0; i < size; i++)
    {
        sum += arr[i];
        if(sum > max_sum)
            max_sum = sum;
        if(sum < 0)
            sum = 0;
    }
    return sum;
}
int main()
{
    int arr[] = {10, 4, 2, 12, 16, 1};
    int p = max_sarr(arr, 6);
    cout << p << endl;
    return 0;
}

The output is 45. So... where is the mistake in my thought process ?

4

2 回答 2

3

你误解了这个问题。问题是找到给定数组的连续子数组，使其具有所有子数组的最高和。也就是说，它基本上会在数组中找到第一个元素和最后一个元素，如果将包括它们之间的元素相加，它将为您提供最大可能值。

如果数组中的所有值都是正数，则最大子数组始终是整个数组。在这种情况下，如果将数组中的所有元素相加，则得到 45。

考虑一个带有 values 的数组{-5, 10, -3, 22}。我们可以枚举它的所有子数组：

Subarrays of length 0: {}
Subarrays of length 1: {-5}             {10}         {-3}     {22}
Subarrays of length 2: {-5, 10}         {10, -3}     {-3, 22}
Subarrays of length 3: {-5, 10, -3}     {10, -3, 22}
Subarrays of length 4: {-5, 10, -3, 22}

和最大的子数组为{10 -3 22}，其和为 29。

于 2013-04-21T13:19:52.450 回答
2

sftrabbit 的答案很棒，但是我强烈推荐CLRS 书页 68 中的最大子数组问题部分。它非常清楚，它还讨论了渐近复杂性和问题的现实生活。

除此之外，正如您所料，一个包含所有正元素的数组，它的最大子数组将是数组本身。

于 2013-04-21T13:32:12.360 回答