53. Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [−2,1,−3,4,−1,2,1,−5,4], the contiguous subarray [4,−1,2,1] has the largest sum = 6.

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        //初始化为最小的int值，避免数组全负数返回0的情况
        int maxSum = INT_MIN;
        int curSum = 0;

        for(int i = 0; i < nums.size(); i++){
            curSum += nums[i];
            std::cout<<i<<" "<<curSum<<std::endl;
            if(curSum > maxSum)
                maxSum = curSum;
            if(curSum < 0)
                curSum = 0;
        }
        return maxSum;
    }
};