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

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

方法:

1. 令max_ending_here 为一个数组，其元素max_ending_here[i] 表示恰好在(不包括在内)之前结束的子数组(可以为空)的最大总和) 索引 i。要计算它，请使用与函数 maxSubArraySum 中相同的方法。时间复杂度O(n)，空间复杂度O(n)。

2. 令sum_from_here 为数组，其元素sum_from_here[i] 表示从(包含的)索引 开始的长度为2 的子数组的总和i，这意味着 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]