所有相邻子阵列的最大和[闭合]

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

考虑数组:{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} 总和:1
   {-2}和:-2
   {3} 总和:3
   {5} 总和:5
   {-4}和:-4
   

看起来最大的总和是8。

你应该在这里看到一个模式,我从数组的长度开始,这里是5 case,并将其减少一,直到我处理了一个元素数组。我还从数组的第零个元素开始,并尝试在给定长度的情况下生成一个有效的数组。例如,如果我使用四个元素数组,从数组元素0开始,它可以通过数组[0]->数组[3]和数组[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( 即 数组[1]、数组[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)编译了这个。