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

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

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

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int N, num, max;
    static int[] maxLength = new int[1001];
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            num = Integer.parseInt(st.nextToken());
            max = 0;
            for (int j = 0; j < num; j++) {
                max = Math.max(max, maxLength[j]);
            }
            maxLength[num] = max + 1;
        }
        System.out.println(Arrays.stream(maxLength).max().getAsInt());
    }
}

💡 DP

뭔가 기존에 알고있는 dp와는 다른 느낌...

풀이

• 해당 수를 끝으로 하는 수열의 최대 길이를 저장하는 배열 선언 : maxLength
  • 배열의 인덱스에 해당하는 수가 최대값인 수열의 길이를 저장함
  • EX) maxLength[30] : 마지막 수가 30인 증가하는 부분수열의 최대 길이
• 특정 수 num이 주어지면 1 ~ num 까지 최대 배열 길이에 +1 한 값이 num이 마지막에 오는 증가하는 부분 수열의 길이