寻找最大子数组的另一种方法

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;
}

- Hem

Answer 1

做法：

1. 定义一个数组 max_ending_here，数组元素 max_ending_here[i] 表示以（但不包括）索引 i 结尾的所有子数组（可以为空）的最大和。为了计算它，请使用与您的函数 maxSubArraySum 中相同的方法。时间复杂度为 O(n)，空间复杂度为 O(n)。

2. 定义一个数组 sum_from_here，数组元素 sum_from_here[i] 表示从（包括）索引 i 开始的长度为 2 的子数组的总和，即 sum_from_here[i] = a[i] + a[i + 1]。时间复杂度为 O(n)，空间复杂度为 O(n)。

3. 遍历所有有效索引，并找到 max_ending_here[i] + sum_from_here[i] 的最大值：这就是你要找的值。时间复杂度为 O(n)，空间复杂度为 O(1)。

因此，总的时间复杂度为O(n)，空间复杂度为O(n)。

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

您在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]

- starrify

---

@Hem 在你后面提供的代码中，数组max_ending_here的计算有误：不要忘记检查if (max_ending_here < 0) max_ending_here = 0;。此外，在第18行的计算表明sum_from_here与max_ending_here重叠，这也是不正确的。 - starrify

Answer 2

你可以通过使用我在这里实现的滑动窗口算法来解决这个问题。

在算法的所有阶段，我们都保持以下内容：

1. 一个窗口[lo...hi]。
2. 当前窗口的总和。
3. 一个名为index的变量，用于跟踪当前窗口中的错误前缀，删除它将增加总和的值。因此，如果我们删除前缀[lo...index]，那么新窗口就变成[index+1 ... hi]，总和会增加，因为[lo...index]有一个负总和。
4. 存储在变量prefixSum中的前缀和。它保存区间[lo...index]的总和。
5. 到目前为止找到的最佳总和。

初始化：

• window =[0 ... 1]
• sum = arr[0] + arr1
• index = 0
• prefixSum = arr[0]

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

• 检查当前窗口是否存在一个前缀，去除该前缀将增加总和的值
• 将列表中的下一个值添加到当前区间中，并更改窗口和总和变量。
• 更新bestSum变量。

以下Java代码示例实现了上述说明。

        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)
空间复杂度： O(1)

- Nikunj Banka