【编程珠玑】第八章 算法设计技术

一，概述

问题：求一维数组中连续子向量的最大和。

例如：a[6]={3,4,-2,-9,10,8}; 则最大连续子向量的和 为 10+8 = 18

1）解法一：简单算法

#include <stdio.h>
#define max(a, b) ((a)>(b)?(a):(b))
int main()
{
    int a[6]={3,4,-2,-9,10,8}; 
    int i,j,k;
    int sum=0;
    int maxsofar=0;

    
	for(i=0;i<6;++i)
	{
		for(j=i;j<6;++j)
		{
			sum=0;
			for(k=i;k<=j;++k)
			{
				sum+=a[k];
			}
			maxsofar=max(maxsofar,sum);
		}
	}
	
	printf("max=%d\n",maxsofar);
	return 0;
}

2）两个平方算法

算法一：

#include <stdio.h>
#define max(a, b) ((a)>(b)?(a):(b))
int main()
{
    int a[6]={3,4,-2,-9,10,8}; 
    int i,j;
    int sum=0;
    int maxsofar=0;

    
	for(i=0;i<6;++i)
	{
		sum=0;
		for(j=i;j<6;++j)
		{
					
		    sum+=a[j];
			maxsofar=max(maxsofar,sum);
		}
	}
	
	printf("max=%d\n",maxsofar);
	return 0;
}

算法二：

#include <stdio.h>
#define max(a, b) ((a)>(b)?(a):(b))
int main()
{
    int a[6]={3,4,-2,-9,10,8};
	int cumarr[6]; cumarr[-1]=0;
    int i,j;
    int sum=0;
    int maxsofar=0;

    for(i=0;i<6;++i)
    {
    	cumarr[i] = cumarr[i-1] + a[i];
    }
	for(i=0;i<6;++i)
	{
		sum=0;
		for(j=i;j<6;++j)
		{
					
		    sum = cumarr[j] - cumarr [i-1];
			maxsofar=max(maxsofar,sum);
		}
	}
	
	printf("max=%d\n",maxsofar);
	return 0;
}

3）分治算法

思想：以m为分界线，最大值有三种情况

一：在m左侧

二：在m右侧

三：跨越m

关键：最初求解左右最大值时候，一定要从中间向两侧递增。看源码解释……

#include "stdio.h"
#define max(a,b)  a>b?a:b

int a[6]={3,4,-2,-9,10,8};
int max2(int a,int b,int c)
{
	if(a>b&&a>c)
		return a;
	else if(b>a&&b>c)
		return b;
	else return c;	
}  
int maxsum(int l,int u)
{
	int i,m,sum,lmax,rmax;
	if(l>u)
		return 0;
	if(l==u)
		return max(0,a[l]);
        m=(l+u)/2;
	
	lmax = sum =0;
	for(i=m;i>=l;--i)
   	{
		sum += a[i];
		lmax =max(lmax,sum);
	}
	
	printf("m=:%d\n",m);
	rmax =sum =0;
	for(i=m+1;i<=u;++i)
	{
		sum += a[i];
		rmax =max(rmax,sum);
	}
	return max2(lmax + rmax , maxsum(l,m) , maxsum(m+1,u) );
}
int main()
{	
	int maxsofar=maxsum(0,5);
	printf("max=%d",maxsofar);
	return 0;
}

【注意】 max2() 如果用宏 #define max(a,b,c) max(a,b) >c?max(a,b):c 则不会得到正确结果

4）扫描算法

#include "stdio.h"
int main()
{	
    int a[6]={3,4,-2,-9,10,8};
	int i,sum=0;
	for(i=0;i<6;++i)
	{
		sum+=a[i];
		if(sum<0)
			sum=0;
	}
	
	printf("max=%d",sum);
	return 0;
}

二，总结

优化算法的策略

1）保存已经计算的状态，避免重复计算。

2）将信息预处理到数据结构中。例如算法二

3）分治算法，采取更高级的算法

4）扫描算法，巧妙

5）下界：证明某个匹配的下界，确定最优算法

三，习题

10）可以采用两种方法：O(n*n)

#include <stdio.h>
#define min(a, b) ((a)>(b)?(b):(a))
#define obs(a) a>0?a:-a
int main()
{
    int a[6]={3,4,-2,-9,10,8}; 
    int i,j,k;
    int sum=0;
    int maxsofar=65535;//这个很关键 

    
	for(i=0;i<6;++i)
	{
		for(j=i;j<6;++j)
		{
			sum=0;
			for(k=i;k<=j;++k)
			{
				sum+=a[k];
			}
			maxsofar=min(maxsofar,obs(sum));
		}
	}
	
	printf("max=%d\n",maxsofar);
	return 0;
}

返回结果是 1

可以采用O(nlogn)的算法

#include <stdio.h>
#define min(a, b) ((a)>(b)?(b):(a))
#define obs(a) a>0?a:-a

/*先将 轴 记录在temp 中 先从后面向前找小于轴的 放到第一个（即轴所在位置）
再从前向后找  大于轴的元素 存放到 上一步找到的小于轴的位置 
总之：要做的是将后面小于轴的 跟 前面大于轴的 做替换 】
当退出while 循环后 因为最后收场的是 i从低端加上来 所以 i 的位置对应 轴最后要存放的位置*/
   
int Partition(int a[],int i,int j)
{
	int temp=a[i];//记录下轴的位置 
	while(i<j)
	{
		while(i<j&&temp<=a[j])//将比轴小的  移动到低端 
		   j--;
     
          a[i]=a[j];//小的 等于后面的大的 (之后的i 会增加)【后面的大的 移动到前面来后 本趟不会再动】 
       
          
        while(i<j&&temp>=a[i])//将比轴大的 移动到高端 【从前往后找 ，找到 小的往后移动】 
           i++;
        
        a[j]=a[i]; // a[j] 存的 上面找到的小的 （在这里改变）小的等于 前面大的 【】 
        
 	  
	}
	a[i]=temp;//轴的位置 
	
	return i;		
}

void Quicksort(int a[],int i,int j)
{
	int p;
	if(i<j)
	{
		 
	    p=Partition(a,i,j);	    
		Quicksort(a,i,p-1);
		Quicksort(a,p+1,j);
	}
}

int main()
{
    int a[6]={3,4,-2,-9,10,8};
	int cumarr[6]; cumarr[-1]=0;
    int i,j;
    int minsofar=65535;

    for(i=0;i<6;++i)
    {
    	cumarr[i] = cumarr[i-1] + a[i];
    }

    Quicksort(cumarr,0,4);   
	
	for(i=0;i<5;++i)
	{
	    minsofar=min(minsofar,obs(cumarr[i+1] - cumarr [i]));	
	}
	
	printf("min=%d\n",minsofar);
	return 0;
}

返回结果是 1

13）最大子数组问题，给定n*n数组，求矩形子数组的最大总和。

详见博客：http://blog.csdn.net/tianshuai11/article/details/7487882