**一. 题目描述** 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; } ~~~ **四. 小结** 该题是一道基础的动态规划题，尽管有多种其他方法可以实现。