最大子列和问题
给定N个整数的序列{A1, A2 ... An}，求函数 f(i, j) = max{0, 从i到jAn的最大值}
方法1：
遍历所有可能的子序列，计算子序列的和
int MaxSubSeqSum1 (int A[], int N) {
int i, j, k, thisSum, maxSum = 0;
for (i = 0; i < N; i++) {
for (j = i; j < N; j++) {
thisSum = 0;
for (k = i; k <= j; k++) {
thisSum += A[k];
}
if (thisSum > maxSum) {
maxSum = thisSum;
}
}
}
return maxSum;
}
复杂度 O(N^3)
缺点：每次计算序列和都从头到尾计算一次。实际上在i相同的时候，计算序列和只需要将当前值加上前一个子序列和就好了。
由此优化方法得到方法二。
方法2：
将当前值加上一次的序列和作为当前序列和。
int MaxSubSeqSum2 (int A[], int N) {
int i, j, k, thisSum, maxSum = 0;
for (i = 0; i < N; i++) {
for (j = i; j < N; j++) {
thisSum = 0;
for (k = i; k <= j; k++) {
thisSum += A[k];
}
if (thisSum > maxSum) {
maxSum = thisSum;
}
}
}
return maxSum;
}
上面的方法还可以继续优化：
方法3: 在线扫描
int MaxSubseqSum3 (int A[], int N) {
int ThisSum = MaxSum = 0;
for (int i = 0; i < N; i++) {
ThisSum += A[i];
if (ThisSum > MaxSum)
MaxSum = ThisSum;
else if (ThisSum < 0)
ThisSum = 0;
}
return MaxSum;
}
增加要求
如果题目不光要求最大序列的和，而且要求给出最大子序列的开始与结束的下标。
只要找对更新左端和右端的位置即可。如下：
for (int i = 0; i < N; i++) {
int templeft = -1;
int left = -1, right = -1;
cin >> tmp;
A.push_back(tmp);
temp += tmp;
if (temp < 0) {
temp = 0;
templeft = i + 1; // 暂时更新左端
} else if (temp > sum) {
sum = temp;
right = i; // 更新右端
left = templeft; // 更新左端
}
}
我是谁？
我是iimT，大学生，技术宅，计算机科技爱好者，电音小王子。
我的博客：www.iimt.me
我在Weibo：@_iimT
我在B站：https://space.bilibili.com/69824765/#/
想看到我的更多更新的话，很乐意你关注我！
你是谁？
欢迎在文后留下评论，一起讨论，欢迎认识新朋友。
如果你也有博客，在分享你的东西，欢迎交流、友链(本人博客底部可申请)。
下一篇见~
