zuichang1.java

计算一个数组中最长子序列

/**
 * @(#)zuichang1.java
 *
 *
 * @author 
 * @version 1.00 2008/10/12
 */


import java.io.*;
import java.util.*;
public class zuichang1{
	static int[] a=new int[10];
	static int[] b=new int[10];//存储最长子序列
	static int[] c=new int[10];//辅助数组
	public static void main(String[] args)throws IOException{
		FileReader input=new FileReader("input.txt");
		Scanner scanner=new Scanner(input);
		for(int j=0;j<a.length;j++)
		a[j]=scanner.nextInt();
              int l=lcs(a,b,c);//调用lcs函数得到最长子序列长度
		for(int i=0;i<l;i++)
		System.out.print(b[i]+" ");//输出最长子序列
		System.out.println();
	}
	public static int lcs(int[] a,int[] b,int[] c){
       //将最长子序列存到数组b，返回最长子序列长度
		int p=0;int j1=0;int i=0;int m=0;	
		while(j1<(a.length-1)){		
			if(a[i]<a[j1+1]){	
			b[m]=a[i];
			m++;
			p++;	
			}
			j1++;
			if(j1>=1)
			if(a[i]<a[j1])
				i=j1;
		}
	 if(i==a.length-1)b[m]=a[a.length-1];
        else if((i<a.length-1)&&(a[i]>a[i+1])){
			b[m]=a[i];
			p++;
			}
		int k=0;
		while(k<(a.length-1)){
			k++;int q=0;int n=0;
			if(k==a.length-1){
				c[0]=a[a.length-1];
				q++;
				if(q>p){
				p=q;
				copy(b,c,p);//将数组c中数字复制到数组b，使数组b始终存储最长子序列
			    break;
			}
		}					
			else if(k<a.length-1){
				int j=0;
			q=0;i=k;j=i;
			while(i<(a.length-1)){	
				if(a[j]<a[i+1]){
				c[n]=a[j];
				q++;n++;
				}
				i++;
				if(i>=1)
				if(a[j]<a[i])
				j=i;
			}	
             if(j==a.length-1)c[n]=a[a.length-1];
			else if((j<a.length-1)&&(a[j]>a[j+1])){		
				c[n]=a[j];
				q++;}
			if(q>p){
				p=q;
				copy(b,c,p);//同上
			}
		}
		}
		return p;
	}
	public static void copy(int[] b,int[] c,int p){
			for(int i=0;i<p;i++)
			b[i]=c[i];
		}
	}