题目
HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了: 在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。 但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2}, 连续子向量的最大和为8(从第0个开始,到第3个为止)。你会不会被他忽悠住？(子向量的长度至少是1)
分析
要求一个数组中连续子数组的最大和，就一定会遍历整个数组，题目没有要求输出这个子数组是什么，所以我们只需要一边遍历一遍记录最大和。
如果我们加上一个数之后，之前子数组的和变大了，我们就认为这个数是对这个和有贡献的，那么就将这个数加到和里面，假如加上一个数之后，整个之前子数组的 和比0还要小，我们就认为这个子数列是没有贡献的，那么就要丢弃之前的子数列。
那么，我们在这个过程中，怎么确定最大值是多少呢?每一次的遍历，我们都记录一个相加的和，然后用另个变量存储最大值，每一次都去比较着两个数，用这个变量存储最大的值。
代码
public class Solution {
public int FindGreatestSumOfSubArray(int[] array) {
if (array == null || array.length == 0) {
return 0;
}
// 记录所有的和
int sum = array[0];
int tempSum = 0;
for(int i = 0; i < array.length; i++){
if (tempSum >= 0) {
tempSum += array[i];
}else{
tempSum = array[i];
}
if (tempSum > sum) {
sum = tempSum;
}
}
return sum;
}
}
在代码中，有需要注意的地方，sum记录的是整个遍历中的最大值，必须要将其开始就设置为array[0]，否在数组全部是负数的时候，会输出0。
有了代码，我们再来看。tempSum的初始值是0，我们不断的遍历，去往tempSum上加上当前遍历的元素，并且和sum比较，始终用sum记录最大值。
如果当前元素加上之后，比tempSum的初始值0还要小，那么久丢弃之前的子数列，将tempSum设置为当前的元素值，接着往下遍历。
