题解 | #连续子数组的最大和#

动态规划。使用遍历array的同时，使用array自身来保存当前连续子数组的和，第i趟遍历时查看前i-1项中最大子数组的和，若其小于0，则将第i项的值作为前i项中最大子数组的和，否则将前i-1项最大子数组的和加上第i项的值作为前i项中最大子数组的和。前i项最大子数组的和保存在数组的第i项中。

class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int> array) {
        int max = array.at(0);
        for(int i = 1;i<array.size();i++){
            if(array.at(i-1) > 0){
                array.at(i) += array.at(i-1);
            }
            else{
                array.at(i) += 0;
            }
            if(array.at(i)>max){
                max = array.at(i);
            }
        }
        return max;
    }
};

下面给出一个二刷时写的版本，虽然结构复杂了，但是运行速度有所提升。

class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int> array) {
        int max;
        int sum = 0;
        for(int i = 0;i < array.size();i++){
            if(i == 0){
                sum = array.at(i);
                max = sum;
            }
            else if(sum < 0){
                sum = array.at(i);
            }
            else if(array.at(i) < 0){
                if(array.at(i) + sum < 0){
                    sum = 0;
                }
                else{
                    sum += array.at(i);
                }
            }
            else{
                sum += array.at(i);
            }
            if(sum > max){
                max = sum;
            }
        }
        return max;
    }
};