[DP]문제#3. 가장 긴 증가하는 부분수열(백준 11053번),자바

 

11053번: 가장 긴 증가하는 부분 수열 (acmicpc.net)

import java.util.Arrays;
import java.util.Scanner;

public class Main {

	static int N;
	static int[] arr;
	static int[] d;
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner in=new Scanner(System.in);
		N=in.nextInt();
		arr=new int[N];
		d=new int[N];
		int answer=0;
		
		Arrays.fill(d, 1);
		
		for(int i=0;i<N;i++) {
			arr[i]=in.nextInt();
		}
		d[0]=1;
		for(int i=1;i<N;i++) {
			for(int j=0;j<i;j++) {
				if(arr[j]<arr[i]) { 
					d[i]=Math.max(d[i], 1+d[j]);
					answer=Math.max(answer, d[i]);
				}
			}
		}
		if(answer==0) answer=1;
		System.out.println(answer);
	}

}