所有连续子数组的最大总和

Question

我有一个练习要解决：“编写一个高效的 C 程序来查找一维整数数组中连续子数组的最大总和。数组的连续子数组定义为元素序列在数组中有效的任何连续索引集中。

让我们以数组{5,-3, 4}为例。可能的连续子数组组合是 {5}、{-3}、{4}、{5,-3}、{-3,4} 和 {5,-3,4}。注意 {5,4} 不是有效的子数组，因为 5 和 4 的索引不是连续的。连续子数组 {5,-3,4} 的和最大和为 6."

我试图解决它，但我意识到我什至没有理解这个问题，因为如果我有一个包含 5 个不同值的数组，结果应该是 10，而我会说 15 (5 个不同的元素 + 1 作为一个整体 + 4 个元素，如果 2 x 2 + 3 如果 3 乘 3 + 2 如果 4 乘 4)。

在尝试编写代码（用 C 语言）之前，我想知道是否有人可以帮助我理解问题本身。

Answer 1

这就是我解决问题的方法。这不一定是最佳解决方案，但我相信它应该可行。

考虑数组：{1, -2, 3, 5, -4} 并考虑如何手写所有子数组：

从 5 元素数组开始：{1, -2, 3, 5, -4} 总和：3
接下来写出 4 元素数组：
{1, -2, 3, 5} 总和：7
{-2, 3, 5, -4} 总和：2
继续 3 元素数组：
{1, -2, 3} 总和：2
{-2, 3, 5} 总和：6
{3, 5, -4} 总和 of:4
现在是 2 元素数组：
{1, -2} 总和：-1
{-2, 3} 总和：1
{3, 5} 总和：8
{5, -4} 总和：1
最后，1 元素数组：
{1} 个总和：1
{-2} 总和：-2
{3} 个总和：3
{5} 总和：5
{-4} 总和：-4

看起来最大的总和是 8。

你应该在这里看到一个模式，我从数组的长度开始，这里是 5 案例，并将它减一，直到我处理了一个元素的数组。我还从数组的第零个元素开始，并尝试在给定长度的情况下创建一个有效数组。例如，如果我使用四个元素数组，从数组元素 0 开始，它可以通过数组 [0] -> 数组 [3] 和数组 [1]-> 数组 [4] 创建一个子数组（这是数组切片，某些语言如 Python 有执行数组切片的明确表示法，C 没有）。生成每个切片后，对元素求和，完成后寻找最大值。

现在，我会像这样编写代码

int main(void)
{
    int array[] = {1, -2, 3, 5, -4};
    int max = -1;                         // will hold largest sum
    int len = sizeof(array)/sizeof(int);  // C-idiom to find length of array

    for(int slen = len; slen > 0; slen--)           // loop for length of sub-arrays
    {
        for(int jdx = 0; jdx+slen <= len; jdx++)   // looping over elements in original array
        {
             int temp = calcSum(array, jdx, slen);
             if(temp > max)
                 max = temp;

        }
    }
    printf("maximum sum of sub-array is: %d\n", max);
}

现在剩下的就是编写calcSum函数了。它需要三个参数 - 第一个是原始数组，第二个是子数组的起始位置，这是子数组的长度。

int calcSum(int* array, int start, int len)
{
    int    sum = 0;
    printf("[%d:%d]: {", start, start+len);
    for(int ndx = 0; ndx < len; ndx++)
    {
        printf("%d,", array[start+ndx]);
        sum = sum + array[start+ndx];
    }

    printf("} the sum is %d\n", sum);
    return sum;
}

我在里面放了几个 printf，这样你就可以看到程序循环时发生了什么。我的切片符号是 [start:length] 所以 [1:3] 是从索引 1 开始的数组，长度为 3 (i.e array[1], array [2], 数组[3]).

将上面的代码编译为 gcc -std=c99 -pedantic -Wall test.c -o temp 并执行它，产生：

D:\Users\******\GNUHome>temp.exe
[0:5]: {1,-2,3,5,-4,} the sum is 3
[0:4]: {1,-2,3,5,} the sum is 7
[1:4]: {-2,3,5,-4,} the sum is 2
[0:3]: {1,-2,3,} the sum is 2
[1:3]: {-2,3,5,} the sum is 6
[2:3]: {3,5,-4,} the sum is 4
[0:2]: {1,-2,} the sum is -1
[1:2]: {-2,3,} the sum is 1
[2:2]: {3,5,} the sum is 8
[3:2]: {5,-4,} the sum is 1
[0:1]: {1,} the sum is 1
[1:1]: {-2,} the sum is -2
[2:1]: {3,} the sum is 3
[3:1]: {5,} the sum is 5
[4:1]: {-4,} the sum is -4
maximum sum of sub-array is: 8

N.B。我在 Windows 7 Professional 上用 gcc 4.8.3 版（来自 mingw）编译了这个。

所有连续子数组的最大总和

Largest sum of all contiguous subarrays

c

arrays

contiguous