Maximum Sum Subarray

LeetCode #53

Description:

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

Example:

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.

Idea:

index从0开始。 keep一个到i的sum，和之前的min sum，两个相减，就是目前最大的continuous sum。

Code:

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if(nums.empty()) return 0;

        int min_sum_sofar=0;
        int sum_sofar=0;
        int max_subsum=INT_MIN;

        for(int i=0; i<nums.size(); ++i){
            sum_sofar += nums[i];
            max_subsum = max(max_subsum, sum_sofar-min_sum_sofar);
            if(sum_sofar<min_sum_sofar){
                min_sum_sofar=sum_sofar;
            }
        }

        return max_subsum;

    }
};