53. Maximum Subarray

一直累加，并记录当前的最大和，如果当前和小于0，那么sum清零

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int sum = 0;
        int m = INT_MIN;
        for(int i = 0; i < nums.size(); i++){
            sum += nums[i];
            m = max(m, sum);
            if(sum < 0)
                sum = 0;
        }
        return m;
    }
};

解法二：
另外一种，用普通DP解
f[i]表示以i结尾的最大连续数组和
f[i] = max{f[i-1] + nums[i], nums[i]}
最后的答案应该遍历一遍f数组，也可以一遍记录着

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        vector<int> dp(nums.size());
        dp[0] = nums[0];
        int res = dp[0];
        for(int i = 1 ; i < nums.size(); i++){
            dp[i] = max(dp[i - 1] + nums[i], nums[i]);
            if(dp[i] > res) res = dp[i];
        }
        return res;
    }
};

解法三：
记录一个最小的sum,然后用当前的sum来减去最小的sum,就是这一段的连续子序列和

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int minsum = INT_MAX;
        int maxsub = INT_MIN;
        int sum = 0;
        for(int i =0; i < nums.size(); i++){
            minsum = min(minsum, sum);
            sum += nums[i];
            maxsub = max(maxsub, sum - minsum);
        }
        return maxsub;
    }
};