最大子列和问题

问题描述

image.png

问题分析

求一个最大子列和，其子列的开头和结尾必然不是负数，怎么能够最快的求出最大子列和呢？解决思路如下

解决思路

1th

最简单最暴力的方法便是求出每一个子列，并且算出每个之列的和

Code

//ElementType可以是任何符合比较要求的数据类型，不一定是整数，可以是浮点数
temp = 0
sum = 0;
ElementType number[ size ];
for(int i  = 0; i < size; i++){
    for(int j = i; j < size; j++){
        for(int k = i; k <= j; k++)
            temp += number[k];
        if( temp > sum )
            sum = temp;
        temp = 0;
        }
}

这个算法简单，暴力，但是就是花费时间太慢了。时间复杂度达到了O(n³)，这是一个难以忍受的结果，如果 n = 10⁶ Emmmmm........

2th

也许你会发现第三个for是多余的，每次计算temp的时候都需要重复计算，所以我们可以对此优化一下

Code

sum = 0;
ElemenType number[size];
for(int i = 0; i < size; i++){
    for(int j = i; j < size; j++){
        temp += number[j];
        if( temp > sum )
           sum = temp;
        }
    temp = 0;
}

去掉了第三个循环时间复杂度变成了O(n²)，比起原来的算法快了n倍。但是时间复杂度为O(n²)的算法仍然没有办法应付很大的数据，不用着急，我们还有一个更好的版本，时间复杂度可以达到O(n)级别

3th

给定序列{ -2, 11, -4, 13, -5, -2 }，其连续子列{ 11, -4, 13 }有最大的和20

思路如下：
我们知道一个最大子列和，其子列的首和尾必然不能是一个负数，所以当我们遍历一个数组的时候遇到正数便可以开始我们的子列了，开始子列之后遇到正数自然好办，一直扩充即可。但是遇到负数怎么办？我们知道最大子列里面是可以包含负数的！但是加入负数也会可能破坏最大子列。我们应该怎么做？所以在这里引入一个gradient，当我们的子列遇到负数时gradient开始发挥作用

经过观察我们发现，负数能不能引入子列。需要看后面有没有正数，并且正数与之前的负数相加可不可以大于或等于零。如果大于或等于零我们便可以将gradient的这些数纳入到到子列。因此gradient用于记录遇到负数之后的数字的和，一旦 gradient >= 0 我们便把gradient的数列加入我们的最大子列，更新一下我们当前子列和并清零gradient

但是只有gradient是不行的，必须要给gradient提供一个上限，如果gradient的绝对值大于当前子列。该子列便不可能再增长了。换句话说，什么时候子列没有增长的可能了就是没有数或者gradient与当前子列和相加小于零！

当gradient与子列和相加小于零时，从哪里开始继续寻找最大子列？从遍历时让子列爆掉的数继续遍历下去直至遇到正数便可，可能有人会问为什么会是在这里，而不是之前的数？

让我们把开始子列的数到爆掉的数分为两块，一块是已经确定的子列，一块是gradient(注意前面所说，当gradient >= 0时，子列便会被扩大，同时gradient清零因此爆掉时，gradient是负数并且绝对值大于子列和)

如果从子列开始重新找最大子列，可是当遇到之前的gradient仍旧会爆掉，因此从子列寻找舍弃，那么gradient呢。gradient虽然可以有正数，但是有了这个正数，仍旧让子列爆掉，所以该正数之后的负数的绝对值显然会比这个正数大

因此我们只需一直往下遍历直至遇到正数开始新的子列即可，这也是为什么这个算法为什么会达到O(n)的原因！我们只需要遍历一遍便可以找到最大子列和

Example:
给定序列{ -2, 11, -4, -1, 13, -5, -2 }（与上的数列不相同）最大子列和为19
step 1>>> -2<0 不开始子列
step 2>>> 11>0 开始子列子列和为11
step 3>>> -4<0 遇到负数，gradient开始工作，记录 -4 但是现在子列还是有增长的可能！子列和为11
step 4>>> -1<0 遇到负数，记录-1，gradient变成 -5 ，子列仍有增长的可能子列和为11
step 5>>> 13>0 遇到正数，gradient与之相加大于0，更新gradient为8，更新子列和，子列和为19 ，gradient清零。Tips：gradient只有大于或等于零才会清零，更新子列和
step 6>>> -5<0 gradient = -5，子列和为19
step 7>>> -2<0 gradient = -7，子列和为19
step 8>>> 没有数字，因此最大子列和为19

Code

#include<stdio.h>
#include<math.h>
int main(void) {
    int mark;
    int length;
    int Max = 0;
    int gradient = 0;
    int number;
    int temp = 0;
    scanf("%d",&length);

    for (int i = 0; i < length; i++) {
        scanf("%d",&number);
        if (number >= 0)
            temp += number;
        else {
            for ( ; i < length; i++) {
                gradient += number;
                if (gradient >= 0) {
                    temp += gradient;
                    gradient = 0;
                }
                else if ( -gradient > temp) {
                    if (Max < temp)
                        Max = temp;
                    gradient = temp = 0;
                    break;
                }
                scanf("%d",&number);
            }
            if (temp > Max)
                Max = temp;
        }
    }
    printf("%d\n", Max);
    return 0;
}

上述代码是实时输入数字，不是从数组获取。但是思路是一样的

解决这个问题的思想可以简述为，但遇到与目标相反的向量时，判断是否大于目标向量。如果大于，便知为当前最大向量。如果小于，便还有可能会继续增长向量

向量是抽象化的说法，因为一时找不到更好的说法在最大子列和问题中，不断扩大子列和便是目标向量，遇到负数便是遇到与目标相反的向量

有了这个思想，最大子列乘积相信你也能解决