查找最大总和连续子数组 - 另一个版本

Question

本论坛有很多寻找最大和连续子数组的帖子。然而，这个问题的一个小变化是，子数组应该至少有两个元素。

例如，对于输入 [-2, 3, 4, -5, 9, -13, 100, -101, 7]，下面的代码给出 100。但是，根据上述限制，子数组 [3, 4, -5, 9 , -13, 100] 将是 98。有人可以帮我做这个吗？我无法为此找到正确的逻辑。

#include<stdio.h>
int maxSubArraySum(int a[], int size)
{
   int max_so_far = 0, max_ending_here = 0;
   int i;
   for(i = 0; i < size; i++)
   {
     max_ending_here = max_ending_here + a[i];
     if(max_ending_here < 0)
        max_ending_here = 0;
     if(max_so_far < max_ending_here)
        max_so_far = max_ending_here;
    }
    return max_so_far;
} 

/*Driver program to test maxSubArraySum*/
int main()
{
   int a[] = {-2, 3, 4, -5, 9, -13, 100, -101, 7};
   int n = sizeof(a)/sizeof(a[0]);
   int max_sum = maxSubArraySum(a, n);
   printf("Maximum contiguous sum is %d\n", max_sum);
   getchar();
   return 0;
}

更新 1： 根据 starrify 进行了更改，但我没有得到我所期望的。它给出 183 而不是 98。

#include<stdio.h>

const int size = 9;

int maxSubArraySum(int a[])
{
    int max_so_far = 0;
    int i;
    int max_ending_here[size];
    int sum_from_here[size];

    max_ending_here[0] = a[0];
    //sum_from_here[0] = a[0] + a[1];

    for (i = 1; i < size; i++)
    {
        max_ending_here[i] = max_ending_here[i-1] + a[i];
        sum_from_here[i] = a[i-1] + a[i];

        if (max_so_far < (max_ending_here[i] + sum_from_here[i]))
            max_so_far = max_ending_here[i] + sum_from_here[i];

    }

    return max_so_far;
}

/*Driver program to test maxSubArraySum*/
int main()
{
    int a[] = { -2, 3, 4, -5, 9, -13, 100, -101, 7 };
    int n = sizeof(a) / sizeof(a[0]);
    int max_sum = maxSubArraySum(a);
    printf("Maximum contiguous sum is %d\n", max_sum);
    getchar();
    return 0;
}

Answer 1

处理方法：

设max_ending_here为一个数组，其元素max_ending_here[i]表示在索引[=14之前（不包括）结束的子数组（可以为空）的最大总和=].要计算它，请使用与函数 maxSubArraySum 中相同的方法。时间复杂度为O(n)，space复杂度为O(n).
令sum_from_here为一个数组，其元素sum_from_here[i]表示从（包含的）索引i开始的长度为2的子数组之和，这意味着sum_from_here[i] = a[i] + a[i + 1]。时间复杂度为O(n)，space复杂度为O(n).
遍历所有有效索引并找到 max_ending_here[i] + sum_from_here[i] 的最大值：该值就是您要查找的值。时间复杂度为O(n)，space复杂度为O(1).

因此整体时间复杂度为O(n)，space复杂度为O(n).

此方法可扩展到任意最小长度——不仅是 2，而且时间和 space 复杂度不会增加。

您在maxSubArraySum中的原始实现实际上是上述方法的一个特例，其中最小子数组长度为0。

已编辑：

根据您在更新 1 中提供的代码，我做了一些更改并在此处提供正确的版本：

int maxSubArraySum(int a[])
{
    int max_so_far = 0;
    int i;
    int max_ending_here[size];
    int sum_from_here[size];

    max_ending_here[0] = 0;
    for (i = 1; i < size - 1; i++)
    {
        max_ending_here[i] = max_ending_here[i - 1] + a[i - 1];
        if (max_ending_here[i] < 0)
            max_ending_here[i] = 0;
        sum_from_here[i] = a[i] + a[i + 1];

        if (max_so_far < (max_ending_here[i] + sum_from_here[i]))
            max_so_far = max_ending_here[i] + sum_from_here[i];

    }

    return max_so_far;
}

注意关键是max_ending_here[i]和sum_from_here[i]不能重叠。这是一个例子：

-2   3   4   -5   9   -13   100   -101   7
   | 3   4   -5   9 | -13   100 |
           |              |
           |              |
          this            |
           is             |
    max_ending_here[5]    |
                          |
                         this
                          is
                    sum_from_here[5]

Answer 2

您可以使用我已经实现 here 的滑动 window 算法来解决这个问题。

在算法的所有时间点，我们都维护以下

A window [lo...hi]。
当前的总和window。
一个名为 index 的变量，用于跟踪当前 window 中的错误前缀，删除会增加总和的值。因此，如果我们删除前缀 [lo...index]，则新的 window 变为 [index+1 ... hi] 并且总和增加，因为 [lo...index] 的总和为负。
存储在变量prefixSum 中的前缀总和。它保存区间 [lo...index].
迄今为止找到的最佳总和。

初始化

window =[0 ... 1]
sum = arr[0] + arr1
指数=0
prefixSum = arr[0]

现在在 while 循环的每次迭代中，

检查当前是否存在前缀 window 删除会增加总和的值
将列表中的下一个值添加到当前区间并更改 window 和 sum 变量。
更新 bestSum 变量。

下面working Java code实现上面的解释

        int lo = 0;
        int hi = 1;
        int sum = arr[0] + arr[1];
        int index = 0;
        int prefixSum = arr[0];

        int bestSum = sum;
        int bestLo = 0;
        int bestHi = 1;

        while(true){
            // Removes bad prefixes that sum to a negative value. 
            while(true){
                if(hi-index <= 1){
                    break;
                }
                if(prefixSum<0){
                    sum -= prefixSum;
                    lo = index+1;
                    index++;
                    prefixSum = arr[index];
                    break;
                }else{
                    prefixSum += arr[++index];
                }
            }

            // Update the bestSum, bestLo and bestHi variables. 
            if(sum > bestSum){
                bestSum = sum;
                bestLo = lo;
                bestHi = hi;
            }

            if(hi==arr.length-1){
                break;
            }

            // Include arr[hi+1] in the current window. 
            sum += arr[++hi];
        }
        System.out.println("ANS : " + bestSum);
        System.out.println("Interval : " + bestLo + " to " + bestHi);

在算法 lo+1<=hi 和 while 循环的每一步中，我们将 hi 递增 1 . 同样，变量 lo 和 index 都不会减少。因此，时间复杂度与输入的大小成线性关系。

时间复杂度：O(n)
Space 复杂度：O(1)

查找最大总和连续子数组 - 另一个版本

Finding a maximum sum contiguous sub array - another version

c++

arrays

algorithm

math

divide-and-conquer