testhechangduixing.java

动态规划之合唱队形,即利用动态规划解决合唱队形的问题

package dynamicprogramming;


public class TestHechangDuixing {

	//计算一个队列排成中间高，两边低的合唱队列的最大人数
	
	public int getGetOutQueueLength(int[] a){
		//a是原始队列
		if(a == null){
			return 0 ;
		}
		int lenth = a.length;
		
		int[] b = new int[lenth];//从左往右的最长上升子序列所含人数
		int[] c = new int[lenth];//从右往左的最长上升子序列所含人数
		int max = 0;
		//求左侧上升子序列
		b[0] = 1;
		for(int i = 1;i <= lenth - 1;i++){
			max = 0;
			for(int j = i-1;j >=1;j--){
				if(a[i] > a[j] && b[j]   > max){
					max = b[j];
				}
			}
			b[i] = max + 1;
		}
		//System.out.println("左侧最长上升子序列:"+b);
		
		//求右侧上升子序列
		c[lenth - 1] = 1;
		for(int i = lenth-2;i >=0;i--){
			max = 0;
			for(int j = i+1;j <= lenth -1;j++){
				if(a[i] > a[j] && c[j]   > max){
					max = c[j];
				}
			}
			c[i] = max + 1;
		}
		//System.out.println("右侧最长上升子序列:"+c);
		//枚举求合唱队的最大人数
		max = 0;
		int middle = 0;
		for(int i = 0;i < lenth - 1;i++){
			if(c[i] + b[i]  > max){
				max = c[i]+b[i];
				middle = i;
			}
		}
		//以下为求合唱队行，因为要经历三个循环，有没有更好的方法？
		int l = middle;
		int r = middle;// 合唱队形的左右边界
		while(c[l-1] < c[l] ){
			l--;
		}
		while(c[r+1] < c[r]){
			r++;
		}
		System.out.print("合唱队形为"+ a[l]);
		for(int i = l+1;i <= r;i++){
			System.out.print("," + a[i]);
		}
		System.out.println("");
		
		return max - 1;
	}
	public static void main(String[] args) {
		TestHechangDuixing testHechangDuixing = new TestHechangDuixing();
		int[] queue = new int[]{186,186,150,200,160,130,197,220};
		System.out.println("合唱队的人数为" + testHechangDuixing.getGetOutQueueLength(queue));
	}
}