Maximum Subarray <LeetCode>

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 };

)