题目描述:
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.
解题思路:
1 class Solution { 2 public: 3 int maxSubArray(vector<int>& nums) { 4 int max_sum = INT_MIN; 5 int sum = 0; 6 for (int i = 0; i < nums.size(); ++i) { 7 sum += nums[i]; 8 if (sum > max_sum) { 9 max_sum = sum; 10 } 11 12 if (sum <= 0) { 13 sum = 0; 14 } 15 } 16 17 return max_sum; 18 } 19 };
原文：http://www.cnblogs.com/skycore/p/5267114.html