[Algo] 백준 11053 가장 긴 증가하는 부분 수열 JAVA

문제 바로가기 : https://www.acmicpc.net/problem/12015

메모리 : 12064KB

시간 : 108ms

언어 : Java 11

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    /*
     * 한 숫자에서 여러 증가수열이 나올 수 있으니까 dp로 최선의 선택을 해야하네
     * 뒤에서부터 내려가면서 찾아보자
     */

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        int[] dp = new int[1001];
        dp[0] = 1;
        int ans = 1;
        for (int i = 1; i < N; i++) {
            int max = 0;
            for (int j = 0; j < i; j++) {
                if (arr[i] > arr[j]) {
                    max = Math.max(max, dp[j]);
                }
            }
            dp[i] = max + 1;
            ans = Math.max(ans, dp[i]);
        }
        System.out.println(ans);
    }
}