c - 所有连续子数组的最大和

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 x 3)+ 2如果四乘四)。

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

Answer 1

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

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

1. 从 5 元素数组开始:{1, -2, 3, 5, -4} 总和:3
   
2. 接下来写出 4 元素数组:
   {1, -2, 3, 5} 总和:7
   {-2, 3, 5, -4} 总和:2
   
3. 继续使用三元素数组:
   {1, -2, 3} 总和:2
   {-2, 3, 5} 总和:6
   {3, 5, -4} 总和:4
   
4. 现在是 2 元素数组:
   {1, -2} 总和:-1
   {-2, 3} 总和:1
   {3, 5} 总和:8
   {5, -4} 总和:1
   
5. 最后是一元素数组:
   {1} 总和:1
   {-2} 总和:-2
   {3} 总和:3
   {5} 总和:5
   {-4} 总和:-4
   

看起来最大的和是8。

你应该在这里看到一个模式，我从数组的长度开始，这里是 5 情况，并将其减一，直到我处理单元素数组。我还从数组的第零个元素开始，并尝试根据给定的长度创建一个有效的数组。例如，如果我正在处理四个元素数组，从数组元素 0 开始，它可以通过 array[0] -> array[3] 和 array[1]->array[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 的数组(即 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

注意我在 Windows 7 Professional 上使用 gcc 版本 4.8.3(来自 mingw)编译了此文件。