在线处理：最大子列和问题

问题

给出一个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)
是最大子列和问题已知的最优解.

原理

• 子列和为负数时无法令当前子列与下一个数的和变大

算法流程

1. 从左向右读取数组
2. 从第一个数加起，如果子列和为正且大于最大子列和，则更新最大子列和，反之令当前子列和为0，继续读入