leetcode 剑指 Offer 42. 连续子数组的最大和

leetcode

1，记录上一次的最大和
C++：

class Solution {
public:
    int maxSubArray(vector<int>& nums) {

        int maxSubArray = nums[0];
        int lastSubArray = maxSubArray;
        for ( int i = 1; i < nums.size(); ++i ) {
            
            if ( lastSubArray < 0 ) {
                
                lastSubArray = nums[i];
                
            } else {
                
                lastSubArray += nums[i];
            }
            
            if ( lastSubArray > maxSubArray ) {
                
                maxSubArray = lastSubArray;
            }
        }
        
        return maxSubArray;
    }
};

2，maxSubArray = sum - minSum
C++：

class Solution {
public:
    int maxSubArray(vector<int>& nums) {

        int maxSubArray = nums[0];
        int minSum = min(maxSubArray, 0);
        int sum = maxSubArray;
        for ( int i = 1; i < nums.size(); ++i ) {
            
            sum += + nums[i];
            maxSubArray = max(maxSubArray, sum - minSum);
            minSum = min(minSum, sum);
        }
        
        return maxSubArray;
    }
};