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.
動態規劃。 對于從0到i，要使得當前的狀態取值最大，那么，對于前一個狀態的最大值，考慮如下兩種情況：
當前一個狀態的最大值為負數時，直接拋棄當前一個狀態的最大值非負時，那么加上它也就是說，有如下的狀態轉移方程：
maxSubArray(A, i) = A[i] + (maxSubArray(A, i - 1) > 0 ? maxSubArray(A, i - 1) : 0)新聞熱點
疑難解答
