最小子列和问题

前言

通过对最小子列和问题四种实现手段浅涉数据结构中关于复杂度知识点的理解

一、题目描述

二、设计步骤

对于该问题，最基本的思路应该是：将所有可能出现的{ i , j }组合产生的结果全部扫描一遍，比较得出最大值。该算法需要三个for循环嵌套语句，复杂度为O(n^3)。

int MaxSubseqSuml(int A[],int N)
{
	int ThisSum,MaxSum = 0;
	int i,j,k;
	
	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;
}

如果改变ThisSum的归零位置，并舍去对从同一个 i 开始的连续元素的重复累加过程，可以减少一层循环，复杂度为O(n^2)。

int MaxSubseqSuml(int A[],int N)
{
	int ThisSum,MaxSum = 0;
	int i,j;
	
	for(i = 0;i < N;i++)
	{
		ThisSum = 0;
		for(j = i;j < N;j++)
		{
			ThisSum += A[j];
			if(ThisSum > MaxSum)
				MaxSum = ThisSum;
		}
	}
	return MaxSum;
}

?若采用分而治之的思路，将 A[] 分为两个子列分别求解，同时不断递归，结合线性表，可以设计出T(n) = O(nlogn)的算法：

int Max3 ( int A, int B, int C ) {
	return (A > B) ? (A > C ? A : C) : (B > C ? B : C);
}

int DivideAndConquer (int List[], int left, int right) 
{
	int MaxLeftSum, MaxRightSum;
	int MaxLeftBorderSum, MaxRightBorderSum;
	
	int LeftBorderSum, RightBorderSum;
	int center, i;
	
	if ( left == right ) {
		if ( List[left] > 0 )	return List[left];
		else return 0;
	}

	center = ( left + right ) / 2;
	MaxLeftSum = DivideAndConquer ( List, left, center );
	MaxRightSum = DivideAndConquer ( List, center+1, right );
	
	MaxLeftBorderSum = 0;	LeftBorderSum = 0;
	for ( i = center; i >= left; i-- ) {
		LeftBorderSum += List[i];
		if ( LeftBorderSum > MaxLeftBorderSum )
			MaxLeftBorderSum = LeftBorderSum;
	}
	
	MaxRightBorderSum = 0;	RightBorderSum = 0;
	for ( i = center+1; i <= right; i++ ) {
		RightBorderSum += List[i];
		if ( RightBorderSum > MaxRightBorderSum )
			MaxRightBorderSum = RightBorderSum;
	}

	return Max3 ( MaxLeftSum, MaxRightSum, MaxLeftBorderSum + MaxRightBorderSum );
}

int MaxSubseqSum3 ( int List[], int N ) {
	return DivideAndConquer ( List, 0, N-1 );
}

?1984年，Jay Kadane运用动态规划的思想，针对该问题提出了更快的算法，即Kadane算法。从数学角度优化了该问题的解答思路，T(n) = O(n)

int MaxSubseqSuml(int A[],int N)
{
	int ThisSum,MaxSum;
	int i;
	
	MaxSum = 0;
	ThisSum = 0;
	for(i = 0;i < N;i++)
	{
		ThisSum += A[i];
		if(ThisSum > MaxSum)
			MaxSum = ThisSum;
		else if(MaxSum < 0)
			ThisSum = 0;
	}
	return MaxSum;
}

该算法的优点不仅在于复杂度小，同时使得MaxSum中存储的值始终为已处理序列部分的解，故又被称为在线处理算法。?

总结

EOF