longestorderedsubsequence.java

来自「PKU中一些数据结构基本算法题的java实现」· Java 代码 · 共 49 行

package PKU.DP;
import java.util.*;


/**
 * ID:2533
 * DP
 * @author yhm
 *
 */
public class LongestOrderedSubsequence {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		while(cin.hasNext()){
			int size = cin.nextInt();
			if(size==0){
				System.out.println(0);
				continue;
			}
			int[] array = new int[size];
			for(int i=0;i<size;i++){
				array[i] = cin.nextInt();
			}
			solve(array,size);
		}

	}

	static void solve(int[] array, int size){
		int[] result = new int[size];
		int max = Integer.MIN_VALUE;
		Arrays.fill(result, 1);
		max = result[0];
		for(int i=1;i<size;i++){
			for(int j=0;j<i;j++){
				if(array[j]<array[i] && result[j]+1>result[i]){
					result[i]=result[j]+1;
					max = Math.max(max, result[i]);
				}
			}
		}
		System.out.println(max);
	}
}