[数据结构与算法]浙江大学《数据结构》Mook网听课笔记及思考之最大子列和问题

最大子列和问题
给定K个整数组成的序列{ $N_1$,$ N_2$, …, $N_K$ }，“连续子列”被定义为{ $N_i$, $N_{i+1}$, …, $N_j$ }，其中 1≤i≤j≤K。“最大子列和”则被定义为所有连续子列元素的和中最大者。例如给定序列{ -2, 11, -4, 13, -5, -2 }，其连续子列{ 11, -4, 13 }有最大的和20。现要求你编写程序，计算给定整数序列的最大子列和。

本题旨在测试各种不同的算法在各种数据情况下的表现。各组测试数据特点如下：

• 数据1：与样例等价，测试基本正确性；
• 数据2：102个随机整数；
• 数据3：103个随机整数；
• 数据4：104个随机整数；
• 数据5：105个随机整数；

输入格式:

输入第1行给出正整数K?(≤100000)；第2行给出K个整数，其间以空格分隔。

输出格式:

在一行中输出最大子列和。如果序列中所有整数皆为负数，则输出0。

输入样例:

6
-2 11 -4 13 -5 -2

输出样例:

20

算法

最大子列和问题的四种算法

暴力枚举

int MaxSubseqSum1( int List[], int N) 
{
	int i, j, k;
	int ThisSum, MaxSum=0;
        
	for(i=0; i<N; i++) {  /* i是子列左端位置 */
		for(j=i; j<N; j++)  {  /* j是子列右端位置 */
		    ThisSum=0;  /*ThisSum是从List[i]到List[j]的子列和 */
	            for(k=i; k<=j; k++) 
			ThisSum+=List[k];
	            if(ThisSum>MaxSum)  /* 如果刚得到的这个子列和更大 */ 
			MaxSum=ThisSum;  /* 则更新结果 */ 
		}  /* j循环结束 */ 
	}  /* i循环结束 */
	return MaxSum;
}

枚举优化

int MaxSubseqSum2( int List[], int N) 
{
	int i, j;
	int ThisSum, MaxSum=0;
	
	for(i=0; i<N; i++) {  /* i是子列左端位置 */
		for(j=i; j<N; j++)  {  /* j是子列右端位置 */
		    /* 对于相同的i，不同的j，只要在j-1次循环的基础上累加一项即可 */
		    ThisSum+=List[j];  /*ThisSum是从List[i]到List[j]的子列和 */
			if(ThisSum>Maxsum)  /* 如果刚得到的这个子列和更大 */ 
			    MaxSum=ThisSum;  /* 则更新结果 */ 
		}  /* j循环结束 */ 
	}  /* i循环结束 */
	return MaxSum;
}

分而治之

int Max3(int A, int B, int C)
{  /* 返回三个整数中的最大值 */
    return A>B ? A : C : B>C ? B : C;	
 } 


int DivideAndConquer( int List[], int Lift, int right) 
{  /* 分治法求List[left]到List[right]的最大子列和 */
	int MaxLiftSum, 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) ;
	MaxLeftSum=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)
		    MaxRightBorder=RightBorderSum;
	 }  /* 右边扫描结束 */
	
	/* 下面返回"治"的结果 */
	return Max3(MaxLeftSum, MaxRightSum, MaxLeftBorderSum+MaxRightBorderSum) ;	
}


int MaxSubseqSum3(int List[], int N)
{  /* 保持与前两种算法相同的函数接口 */
	return DivideAndConquer(List, 0, N-1);
}

在线处理

int MaxSubseqSum4( int List[], int N) 
{
	int i;
	int ThisSum, MaxSum;
    
        ThisSum=Maxsum=0;
	for(i=0; i<N; i++) {  /* i是子列左端位置 */
	    ThisSum+=List[i] /* 向右累加 */
	    if(ThisSum>MaxSum) 
	        MaxSum=ThisSum;
	    else if(ThisSum<0)
	        ThisSum=0;  /* 则不可能使后面的部分和增大，抛弃之 */ 
	}  /* i循环结束 */
	return MaxSum;
}