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: dp.
1 class Solution { 2 public: 3 int maxSubArray(int A[], int n) { 4 int dp = A[0]; 5 int res = A[0]; 6 for(int i = 1; i < n; i++) { 7 dp = max(A[i], A[i] + dp); 8 res = max(res, dp); 9 } 10 return res; 11 } 12 };
Maximum Subarray,布布扣,bubuko.com
原文：http://www.cnblogs.com/zhengjiankang/p/3646876.html