**一. 題目描述** 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)。假設已知`0, .., k`的最大和`sum[k]`以后，則`0, ..., k+1`的最大和sum[k+1]分為以下兩種情況：? 1）若`sum[k]>=0`，則`sum[k+1]=sum[k]+A[k+1]`。? 2）若`sum[k]<0`，另起一個SubArray，令`sum[k+1]=A[k+1]`。 在計算過程中，使用一個變量`maxsum`用于存儲`sum`的最大值，一旦出現更大的`sum`值則更新之，最后返回該變量即可。 **三. 示例代碼** ~~~ int maxSubArray(int A[], int n) { if (n <= 0) return 0; int sum = 0; int maxsum = INT_MIN; for (int i = 0; i < n; i++) { sum += A[i]; if (sum > maxsum) maxsum = sum; if (sum < 0) sum = 0; } return maxsum; } ~~~ **四. 小結** 該題是一道基礎的動態規劃題，盡管有多種其他方法可以實現。