백준 동적 계획법 - 11053번 : 가장 긴 증가하는 부분 수열

https://www.acmicpc.net/problem/11053

11053번: 가장 긴 증가하는 부분 수열

---

import java.io.*;
import java.util.*;
public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int n = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		int[] num = new int[n+1];
		int[] memo = new int[n+1];
		for(int i=1; i<=n; i++) {
			num[i] = Integer.parseInt(st.nextToken());
		}
		int max = -1;
		for(int i=1; i<=n; i++) {
			for(int j=1; j<i; j++) {
				if(num[j]<num[i]) {
					memo[i] = Math.max(memo[j]+1,memo[i]);
				}
			}
			if(memo[i]==0) memo[i] = memo[0]+1;
			if(max<memo[i]) {
				max = memo[i];
			}
		}
		bw.write(max+"");
		bw.close();
	}
	
}