53. Maximum Subarray

我會分成四種情況

1. sum < 0, nums[i] >= 0
代表我們可以不要歷史的和, sum = nums[i]
2. sum > 0, nums[i]< 0
可以加一下, 說不定在未來有機會遇到更大的值
3. sum > 0, nums[i] >= 0, 加完全不吃虧, 加!
4. sum < 0, nums[i] < 0, 比爛的, 就挑負數不要那麼小的吧
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int sum = INT_MIN;
        int res = INT_MIN;
        for(int i = 0; i < nums.size();i++){
            if(sum < 0 && nums[i] >= 0){
                sum = nums[i];
            }else if(sum > 0 &&nums[i] >= 0){
                sum += nums[i];
            }else if(sum >0 && nums[i] < 0){
                sum += nums[i];
            }else{
                sum = max(nums[i], sum);
            }
            res = max(res, sum);
        }
        return res;
    }
};

有個更聰明的解法, 只要sum是負數, 就把sum跟res比完後歸零, 下一輪也是是在比一次負數的大小

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