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.

思路：依次遍历输入数组，若i-1处的和curMax为正，则i处的和应为curMax + A[i]；否则，i处的和为A[i]本身，此时，前i-1个数不会对i及后续数的最大和产生影响。

 1 class Solution { 2 public: 3     int maxSubArray( int A[], int n ) { 4         int maxSum = A[0], curMax = A[0]; 5         for( int i = 1; i < n; ++i ) { 6             curMax = curMax < 0 ? A[i] : curMax + A[i]; 7             if( maxSum < curMax ) { maxSum = curMax; } 8         } 9         return maxSum;10     }11 };

Maximum Subarray