- 问题描述
给定n个数(可以为负数)的序列(a1,a2,…,an)，求$max(0,sum_{k=i}^{j} a_k)space 1≤i≤j≤n$ - 子问题界定
设前边界为1,后边界为i,且$C[i]$是以$A[i]$为结尾的连续子段的和的最大值. - 递推方程
$$C[i]=max(C[i-1]+A[i],A[i]) space i=2,…,n$$
$$C[1]=max(A[1],0)$$ - 时间复杂度:$O(n)$
- 代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
using namespace std;
int (const int A[], int n)
{
int tempSum = 0;
int maxSum = 0;
for (int j = 0;j < n;j++)
{
tempSum = (tempSum + A[j]) > A[j] ? (tempSum + A[j]) : A[j];
if (tempSum > maxSum) // 更新最大和
maxSum = tempSum;
}
return maxSum;
}
int main()
{
const int a[] = { 4, -3, 5, -2, -1, 2, 6, -2 };
int maxSubSum = MaxSubsequenceSum(a, 8);
cout << "The max subsequence sum of a is: " << maxSubSum << endl;
system("pause");
return 0;
}
近期评论