算法分析部分

源代码在线查看: 最大子段和.cpp

软件大小: 23 K
上传用户: lilacky
关键词: 算法分析
下载地址: 免注册下载 普通下载 VIP

相关代码

				#include
				using namespace std;
				
				/*
				给定由n个整数(可能为负整数)组成的序列a1,a2,...,an,求该序列形如{ak和}i				当所有整数均为负数的时候定义其最大子段和为0。依此定义,所求的最优值为
				max{0,max(1				例如,当(a1,a2,a3,a4,a5,a6)=(-2,11,-4,13,-5,-2)时最大子段和为11 + -4 + 13 = 20 
				*/
				
				/*
				最大子段和的简单求法
				*/
				/*
				int MaxSum( int n, int *a, int &besti, int& bestj )
				{
					int sum = 0;
					for( int i = 1; i 					{
						for( int j = i; j 						{
							int thissum = 0;
							for( int k = i; k 							{
								thissum += a[k];
							}
							//对于每一个i开始到j都求这个序列的和
							if ( thissum > sum )
							{
								sum = thissum;
								besti = i;
								bestj = j;
							}
						}
					}
					return sum;
				}
				*/
				/*
				利用已经计算的结果改进算法得到
				*/
				/*
				int MaxSum( int n, int *a, int &besti, int& bestj )
				{
					int sum = 0;
					for( int i = 1; i 					{
						int thissum = 0;
						for( int j = i; j 						{
							thissum += a[j];
							//利用已经计算好的thissum,避免每次都重复计算
							if ( thissum > sum )
							{
								sum = thissum;
								besti = i;
								bestj = j;
							}
						}
					}
					return sum;
				}*/
				
				/*
				最大子段和问题的分治算法
				针对最大子段问题和这个具体问题,本身的结构,我们可以从算法设计的策略上对上述O(n^2)
				计算时间的算法进行进一步的改进。从问题的解的结构可以看出,它适合分治法求解:
				如果将所给的序列a[1:n]分为长度相等的两段a[1:n/2]和a[n/2 + 1:n],分别求出这两段的最大子段和
				,则a[1:n]的最大子段和有三种情形:
				(1)a[1:n]的最大子段和与a[1:n/2]的最大子段和相同
				(2)a[1:n]的最大子段和与a[n/2:n]的最大子段和相同
				(3)a[1:n]的最大子段和为{ak}i				(1)(2)两种情形可以递归求得。情形(3),容易看出a[n/2]与a[n/2+1]在最优子序列中。因此
				,我们可以在a[1:n/2]中计算出s1 = {1 				出s2 = {n/2 + 1 				*/
				
				int MaxSubSum( int *a, int left, int right )
				{
					int sum = 0;
					if ( left == right )
					{
						sum = a[left] > 0 ? a[left]:0;
					}
					else
					{
						int center = ( left + right ) / 2;
						int leftsum = MaxSubSum( a, left, center );
						int rightsum = MaxSubSum( a, center + 1, right );
				
						int lefts = 0;
						int s = 0;
						for( int i = center; i >= left; --i )
						{
							lefts += a[i];
							if ( lefts > s )
							{
				
								s = lefts;
							}
						}
				
						int rights = 0;
						int rs = 0;
						for( i = center + 1; i < right; ++i )
						{
							rights += a[i];
							if ( rights > rs )
							{
								rs  = rights;
							}
						}
				
						sum = rs + s;
						if ( sum < leftsum )
						{
							sum = leftsum;
						}
						if ( sum < rightsum )
						{
							sum = rightsum;
						}
					}
					return sum;
				}
				
				int MaxSum( int n, int *a )
				{
					return MaxSubSum( a, 1, n );
				}
				
				
				/*
				最大子段和问题的动态规划算法
				
				在对上述的分治理算法的分析中,我们注意到,
				若记b[j] = {从(1-j)中的下标开始到j的子段和中最大值}{1				也就是以a[j]为结尾的最大子段和
				整体最大子段和为:
				max{b[j]}{1				因此,当b[j-1]>0时b[j] = b[j-1] + a[j],否则b[j] = a[j]。由此
				得到计算b[j]的动态规划递归式:
				b[j] = max{b[j-1] + a[j],a[j]},1				*/
				
				/*
				int MaxSum( int n, int *a, int &besti, int &bestj )
				{
					int sum = 0;
					int b = 0;
					int flag = 0;
					for( int i = 1; i 					{
						if ( !flag )
						{
							besti = i;
							bestj = i;
							flag = 1;
						}
				
						if ( b > 0 )
						{
							b += a[i];
						}
						else
						{
							besti = i;
							bestj = i;
							b = a[i];
						}
						//calculate b[i]
						if ( b > sum )
						//record the max b[i] by variable sum
						{
							bestj = i;
							sum = b;
						}
					}
				
					return sum;
				}*/
				
				/*
				最大子段和问题与动态规划算法的推广
				(1)最大子矩阵和问题:给定一个m行n列的整数矩阵A,试求矩阵A的一个子矩阵
				使各元素之和最大。
				用二维数组a[1:m][1:n]表示给定的m行n列的整数矩阵。
				子数组a[i1:i2][j1:j2]表示左上角
				和右下角行列坐标分别为(i1,j1)和(i2,j2)的子矩阵。
				
				注意到
				max{1				= max{1				= max{1				
				其中,t(i1,i2) = max{1				=max{1				设b[j] = a[i][j],
				则t(i1,i2) = max{1				
				//先在同一行内,行范围确定情况下,找出列的最大字段和转换为一维的
				//之后再求出行范围的最大字段和,哪些行在一起的总和是最大的
				//b[j]记录的就是在行范围确定下第J列的总和
				//列方向的最大字段和就是求b[j]的最大字段和,如果b[j]的最大字段和求到,就能确定J的
				范围了。之后再求t[i][j]在行上的最大字段和,因为此时J已经确定
				*/
				int MaxSum2( int m, int n, int **a )
				{
					int sum = 0;
					int *b = new int[n+1];
					for( int i = 1; i 					//1					{
						for( int k = 1; k 						{
							b[k] = 0;
						}
				
						for( int j = i; j 						//i						{
							for( int k = 1; k 							{
								b[k] += a[j][k];
								//i1...i2
							}
							//j是行的增加来决定b数组的增长
							int max = MaxSum( n, b );
							//b[1]...b[n]的最大子段和
							if ( max > sum )
							{
								sum = max;
								//sum的值始终记录的是一个最大的
							}
						}
					}
					return sum;
				}
				
				/*
				最大m子段和问题:
				给定由n个整数(可能为负数)组成的序列a1,a2,...,an,以及一个正整数m,
				要求确定序列a1,a2,...,an的m个不相交子段
				使得这m个子段的总和达到最大。
				
				最大m子段和问题是最大子段和问题在子段个数上的推广。
				设b(i,j)表示数组a的前j项中i个子段和的最大值,且第i个子段含a[j](1				则所求的最优值显然为max(m				与最大子段和问题类似地
				b(i,j) = max( b(i,j-1) + a[j], max{i-1				其中b(i,j-1)+a[j]项表示第i个子段含a[j-1],
				而max{i-1				仅含a[j]。初始时b(0,j) = 0,(1				b(i,0) = 0(1				*/
				
				int MaxSumMore( int m, int n, int *a )
				{
					if ( n < m || m < 1 )
					{
						return 0;
					}
					int **b = new int*[m+1];
					for( int i = 0; i 					{
						b[i] = new int[n+1];
					}
					for( i = 0; i 					{
						b[i][0] = 0;
					}
					for( int j = 1; j 					{
						b[0][j] = 0;
					}
					for( i = 1; i 					{
						for( int j = i; j 						//至少要留有n-(m-i)项,如果没有,说明根本不能分成m段,b[i][j]是
						//包含a[j]在内的前i个子段的和
						{
							if ( j > i )
							{
								b[i][j] = b[i][j-1] + a[j];
								//先假设第I个子段包含a[j]
								for( int k = i - 1; k < j; ++k )
								{
									if ( b[i][j] < b[i-1][k] + a[j] )
									{
										b[i][j] = b[i-1][k] + a[j];
									}
									//从i-1到j之间找到最大的b[i-1][k],也就是包含i-1个子段和
									//的最大的一个
								}
							}
							else
							{
								b[i][j] = b[i-1][j-1] + a[j];
							}
						}
					}
					int sum = 0;
					for( j = m; j 					{
						if ( sum < b[m][j] )
						{
							sum = b[m][j];
						}
					}
					return sum;
				}
				
				/*
				注意到上述算法中,
				计算b[i][j]时只用到数组b的第i-1行和第i行的值。
				因而算法中只要存储数组b的当前行,不必存储整个数组。
				另一方面,max{i-1				预先保存起来。这样一来,在计算第i行的值时不必重新计算,节省了计算时间和空间。
				按此思想可对上述算法
				做进一步的改进。
				*/
				
				int MaxSumMore1( int m, int n, int *a )
				{
					if ( n < m || m < 1 )
					{
						return 0;
					}
				
					int *b = new int[n+1];
					//b[i]用来记录前i项中最
					int *c = new int[n+1];
					b[0] = 0;
					c[1] = 0;
					for( int i = 1; i 					{
						b[i] = b[i-1] + a[i];
						//b[i]等同与b[i][i]
						c[i-1] = b[i];
						//相当前i项中前i-1个子段和的最大值
						int max = b[i];
						for( int j = i + 1; j 						{
							b[j] = b[j-1] > c[j-1] ? b[j-1] + a[j] : c[j-1] + a[j];
							//b[j]等同于b[i][j],前j项中前i个子段的最大和
							c[j-1] = max;
							//前j-1项中前i-1个子段的和
							if ( max < b[j] )
							{
								max = b[j];
							}
						}
						c[i+n-m] = max;
						//前i+n-m项中,前i个子段的最大和
					}
				
					int sum = 0;
					//b[j]中记录的都是b[m][j]的值
					for( int j = m; j 					{
						if ( sum < b[j] )
						//b[j]中记录了前j项数据中,m个最大子段和
						{
							sum = b[j];
						}
					}
				
					return sum;
				}
				
				int main()
				{
					cout					int n = 6;
					int *a = new int[n+1];
					a[0] = 0;
					a[1] = -2;
					a[2] = 11;
					a[3] = -4;
					a[4] = 13;
					a[5] = -5;
					a[6] = -2;
					int besti,bestj;
					//int sum = MaxSum( n, a, besti, bestj );
					//int sum = MaxSum( n, a );
					int sum = MaxSumMore1( 3, 6, a );
					cout					cout					cout					
					//MaxSum( int m, int n, int *a );
					return 0;
				}			

相关资源