在线处理:最大子列和问题
问题
给出一个List,求出在这个List中连续几个子列和最大时,最大的子列和的值。
I/O
In:列表 A[],列表长度N
Out:列表A的最大子列和
算法实现
int MaxSubaseqSum(int A[], int N)
/* 求最大连续子列和 最优算法 “在线算法” */
{
int ThisSum, MaxSum;
int i;
ThisSum = MaxSum = 0;
for (i = 0; i < N; i++) {
ThisSum += A[i];
if (ThisSum > MaxSum)
MaxSum = ThisSum;
else if (ThisSum < 0)
ThisSum = 0;
}
return MaxSum;
}
这个算法最大的特点是,无论在任何时候都能返回对于当前而言的正确结果
分析
时间复杂度&空间复杂度
T(N) = O(N)
是最大子列和问题已知的最优解.
原理
- 子列和为负数时无法令当前子列与下一个数的和变大
算法流程
- 从左向右读取数组
- 从第一个数加起,如果子列和为正且大于最大子列和,则更新最大子列和,反之令当前子列和为0,继续读入