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.
算法：用动态规划进行求解，时间复杂度是O(n
1 class Solution { 2 public: 3 int maxSubArray(int A[], int n) { 4 if(n==1) return A[0]; 5 int b; 6 int max=INT_MIN; 7 b=A[0]; 8 if(b>max) max=b; 9 for(int i=1;i<n;i++) 10 { 11 if(b<0) b=A[i]; 12 else b=b+A[i]; 13 if(b>max) max=b; 14 } 15 return max; 16 } 17 };
)
原文：http://www.cnblogs.com/sqxw/p/3947701.html