題目描述

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，要使得當前的狀態取值最大，那么，對于前一個狀態的最大值，考慮如下兩種情況：

也就是說，有如下的狀態轉移方程：

AC代碼