问题描述：
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.
思路：
定义f(i)为array[0...i]的最大子数组。
状态转移方程：
f(i) = i; f(i - 1) <= 0
f(i) = f(i-1) + i; f(i - 1) > 0
解决：
1 class Solution { 2 public: 3 int maxSubArray(vector<int>& nums) { 4 int maxSum = nums[0]; 5 for (int i = 1; i < (nums.size()); i++) 6 { 7 if (nums[i-1] <= 0) 8 nums[i] = nums[i]; 9 else 10 nums[i] = nums[i-1] + nums[i]; 11 maxSum = max(maxSum, nums[i]); 12 } 13 14 15 return maxSum; 16 } 17 };
原文：http://www.cnblogs.com/gatsbydhn/p/4970345.html