55. 连续子数组的最大和

题目链接

记录一下经典题标程。

思路

贪心做法：先加上一个数，如果小于0就直接remake。因为完全没必要将负数放在第一个，去掉反而会更好。

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int res = -0x3f3f3f3f, sum = 0;
        for(int i = 0,tmp = 0; i < nums.size(); i++){
            sum += nums[i];
            res = max(res,sum);
            if(sum < 0) sum = 0;
            //如果nums全为负数则返回最大的负数
        }
        return res;
    }
};

dp做法略。