polymax.java

《算法设计与分析》王晓东编著

public class PolyMax {
	
	static int n;
	static int m[][][];
	static int minf,maxf;
	static char op[];
	static int v[];
	
	private static void minMax(int i,int s,int j)
	{
		int []e=new int[5];
		int a=m[i][s][0],
		    b=m[i][s][1],
		    r=(i+s-1)%n+1,
		    c=m[r][j-s][0],
		    d=m[r][j-s][1];
		if (op[r]=='+') {
			minf=a+c;
			maxf=b+d;
		}
		else
		{
			e[1]=a*c;
			e[2]=a*d;
			e[3]=b*c;
			e[4]=b*d;
			minf=e[1];
			maxf=e[1];
			for (int k=2;k<5;k++) {
				if (minf>e[k]) minf=e[k];
				if (maxf<e[k]) maxf=e[k];
			}
		}
	}
	
	public static int polyMax()
	{
		for (int j=2;j<=n;j++)
		  for (int i=1;i<=n;i++)
			for (int s=1;s<j;s++) {
				minMax(i,s,j);
				if (m[i][j][0]>minf) m[i][j][0]=minf;
				if (m[i][j][1]<maxf) m[i][j][1]=maxf;
			}
		int temp=m[1][n][1];
		for (int i=2;i<=n;i++)
			if (temp<m[i][n][1]) temp=m[i][n][1];
		return temp;		
	}

	public static void main(String[] args) {
		// 初始化op数组,v数组,这两个数组的元素从下标1开始有效
		op=new char[]{' ','+','*','+','*','*'};
		v=new int[]{0,1,2,10,3,-5};
		n=op.length-1;
		
		// 初始化m数组
		m=new int[n+1][n+1][2];		
		for (int i=1;i<=n;i++)
			m[i][1][0]=m[i][1][1]=v[i];
		
		// 计算并输出最高分数
		System.out.println(polyMax());
	}
}