问题描述
问题分析
求一个最大子列和，其子列的开头和结尾必然不是负数，怎么能够最快的求出最大子列和呢？解决思路如下
解决思路
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(n3)，这是一个难以忍受的结果，如果 n = 106 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(n2)，比起原来的算法快了n倍。但是时间复杂度为O(n2)的算法仍然没有办法应付很大的数据，不用着急，我们还有一个更好的版本，时间复杂度可以达到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;
}
上述代码是实时输入数字，不是从数组获取。但是思路是一样的
解决这个问题的思想可以简述为，但遇到与目标相反的向量时，判断是否大于目标向量。如果大于，便知为当前最大向量。如果小于，便还有可能会继续增长向量
向量是抽象化的说法，因为一时找不到更好的说法 在最大子列和问题中，不断扩大子列和便是目标向量，遇到负数便是遇到与目标相反的向量
有了这个思想，最大子列乘积相信你也能解决
