[第8章]算法设计技术——一维模式识别

第八章主要介绍了一维模式识别的算法改进过程。问题输入：n个浮点数的向量x。问题输出：任何连续子向量中的最大和。

（1）首先从最直观的做法入手，就是枚举所有情况下的子向量的和，最后比较出最大的和。首先，利用两层for循环，列出了所有可能的子向量，在用一层for循环，求出子向量的和。运算时间为O(n^3)。

int MaxNum1(int* a,int _len)
 {
	 int maxNum=0;
	 for(int i=0;i<_len;i++)
	 {
		 for(int j=i;j<_len;j++)
		 {
			 int tNum=0;
			 for(int k=i;k<=j;k++)
			 {
				 tNum+=a[k];
			 }
			 maxNum=maxNum>tNum?maxNum:tNum;
		 }
	 }
	 return maxNum;
 }

接下来，作者开始引导我们对算法本身进行分析，去仔细观察，哪些地方是没必要的，可以进行优化。这个时候的一个思路就是，避免重复运算。根据这个思路，我们观察最内层循环，可以发现，每次都要重新计算求子向量的和，下一个子向量的和其实只需要在前一个子向量的和的基础上再加一项即可。这时候，就引出了方案2。

（2）首先求出从首项开始，到任意一项的子向量的和。那么整个向量中的任意一子向量的和其实就是两个从首项开始的子项的差。上代码。该代码时间复杂度为O(n^2)。

 int MaxNum2(int* a,int _len)
 {
	 int* num=new int[_len];
	 for(int i=0;i<_len;i++)
		 num[i]=0;
	 //注意，此处给num[-1]赋0；
         num[-1]=0;

	 for(int i=0;i<_len;i++)
	 {
		 num[i]=num[i-1]+a[i];
	 }
	 
	 int maxNum=0;
	 for(int i=0;i<_len;i++)
		 for(int j=i;j<_len;j++)
			 maxNum=maxNum>(num[j]-num[i-1])?maxNum:(num[j]-num[i-1]);
	 return maxNum;
 }

(3)这时候，对于我来说似乎就没思路了。看作者的介绍，就引出了算法设计当中的重要思想，分治法。该算法的时间复杂度为O(nlogn)。分治法的关键在于如何把问题划分成对应的子问题，以及递归终止条件。在这里，把向量由中点处分成三个部分：中点左侧最大和子向量，过中点的最大子向量，中点右侧最大子向量。对于左侧和右侧，进行递归。

 int MaxNum(int* a,int l,int u)
 {
   //递归终止条件
	 if(l>=u)
		 return a[l];
	//开始递归
	 int leftMax=0;
	 int rightMax=0;
	 int m=(l+u)/2;
	 //从中点开始向左，最大值。
	 int leftNum=0; 
	 for(int i=m;i>=l;i--)
	 {
		 leftNum+=a[i];
		 leftMax=leftMax>leftNum?leftMax:leftNum;
	 }
	 //从中点向右，最大之。
	 int rightNum=0;
	 for(int i=m+1;i<=u;i++)
	 {
		 rightNum+=a[i];
		 rightMax=rightMax>rightNum?rightMax:rightNum;
	 }
	 //得出包含中点的子向量的最大值
	 int mMax=leftMax+rightMax;
	 //递归求出中点左右侧各自的最大子向量和
	 int lMax=MaxNum(a,l,m);
	 int uMax=MaxNum(a,m+1,u);
	 //求三者中的最大值
	 int Max=lMax>uMax?lMax:uMax;
	 Max=Max>mMax?Max:mMax;
	 return Max;
 }

 int MaxNum3(int* a,int _len)
 {
	 return MaxNum(a,0,_len-1);
 }

（4）扫描算法。假设我们已知x[n-1]为止的子向量的最大值，要求到x[n]为止的子向量的最大值。那么，就有两种情况：要么最大子向量包含x[n]，或者不包含。如果不包含，就意味着是到x[n-1]为止的子向量的最大值，前面已求得。如果包含，则意味着这个最大值时从x[n]开始往前推求得的值。我们同时假设我们知道从x[n-1]开始往前的子向量的最大值。

一开始的时候，理解错误了。

//错误理解
int MaxNumX(int* a,int _len)
 {
	 int maxAgg=0;
	 int maxEnd=0;
	 for(int i=0;i<_len;i++)
	 {
		 int sum=0;
		 for(int j=i;j>=0;j--)
		 {
			 sum+=a[j];
			 if(sum>maxEnd)maxEnd=sum;
		 }
		 maxAgg=maxAgg>maxEnd?maxAgg:maxEnd;
	 }
	 return maxAgg;
 }

正确代码如下：

int MaxNumXX(int* a,int _len)
 {
	 int maxAgg=0;
	 int maxEnd=0;
	 for(int i=0;i<_len;i++)
	 {
		 maxEnd=(maxEnd+a[i])>0?(maxEnd+a[i]):0;
		 maxAgg=maxAgg>maxEnd?maxAgg:maxEnd;
	 }
	 return maxAgg;
 }