[LeetCode] 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.

Analysis: This is typical DP problem. Let D[i] be the maximum subarray that ends at index i. Then, D[i+1] = max(D[i] + nums[i], nums[i]). Max(D[i]) will be the result.

    int maxSubArray(vector<int>& nums) {
        int len = nums.size();
        if(0 == len) return 0;

        vector<int> rec(len,0);

        rec[0] = nums[0];
        for(int i=1;i<len;i++)
        {
            rec[i] = max(rec[i-1] + nums[i], nums[i]);
        }        
        return *max_element(rec.begin(), rec.end());
    }

Look at the code. Actually, the max subarray can be obtained from the adjacent elements

    int maxSubArray(vector<int>& nums) {
        int len = nums.size();
        if(0 == len) return 0;
        int maxSub = nums[0];
        int res = maxSub;
        for(int i=1;i<len;i++)
        {
            maxSub = max(nums[i] + maxSub, nums[i]);
            res = max(maxSub, res);
        }
        return res;
    }