Problem statement:
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.
Solution:
The problem wants the max sum of a subarray. The basic idea is to drop the array if its sum is negative.
There two variables: one is the current sum, another is the max sum. The idea is similar with 300. Longest Increasing Subsequence.
Time complexity is O(n).
class Solution { public: int maxSubArray(vector<int>& nums) { int cur_sum = 0; int max_sum = INT_MIN; for(auto num : nums){ if(cur_sum < 0){ // cur_sum < 0, drop off it and make cur_sum = num cur_sum = num; } else { // if cur_sum >= 0, add num to cur_sum cur_sum += num; } // update the max sum for each element max_sum = max(max_sum, cur_sum); } return max_sum; } };
原文：http://www.cnblogs.com/wdw828/p/6876208.html