剑指Offer：30 连续子数组的最大和(最大子列和)

 最大子列和问题，陈越老师的数据结构课第一节里就讲过，照着原来的代码写一遍发现出了问题：

1、一开始忘了初始化maxSum，导致里面是一个随机且很大的数，所以出错。

2、处理了问题1之后，只通过了1/3的case，原因是都为负数的时候返回值为0。

class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int> array) {
        int n = array.size();
        if(array.empty()) return 0;
        
        int thisSum =0, maxSum = 0;
        for(int i=0; i<n; i++)
        {
            thisSum += array[i];
            if(thisSum > maxSum){
                maxSum = thisSum;
            }
            else if(thisSum<0){
                thisSum = 0;
            }
        }
        return maxSum;
    }
};

 照搬原来的代码行不通了，需要在原来的代码基础上改进。

看了书上的动态规划的思路，对之前的“在线式”算法，作了一些改动，即可通过。

class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int> array) {
        int n = array.size();
        if(array.empty()) return 0;
        
        int curMaxSum =array[0], maxSum = array[0];
        for(int i=1; i<n; i++)
        {
            if(curMaxSum<=0){
                curMaxSum = array[i];
                if(maxSum<array[i]) maxSum = array[i];
            }
            else{
                curMaxSum += array[i];
                if(curMaxSum>maxSum) maxSum = curMaxSum;
            }
        }
        return maxSum;
    }
};

当然书上的代码写法更简洁，尤其是初始值选取的很恰当：

class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int> array) {
        int n = array.size();
        if(array.empty()) return 0;
        
        int curMaxSum = 0;
        int maxSum = 0x80000000; //初始值设为32位int变量的最小值
        for(int i=0; i<n; i++)
        {
            if(curMaxSum<=0)
                curMaxSum = array[i];
            else
                curMaxSum += array[i];
            
            if(curMaxSum>maxSum) 
                maxSum = curMaxSum;
        }
        return maxSum;
    }
};