Maximum Subarray（最大子串和问题）
最后更新于：2022-04-01 22:56:59
**一. 题目描述**
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;
}
~~~
**四. 小结**
该题是一道基础的动态规划题，尽管有多种其他方法可以实现。
';