[백준/DP] 11053번 가장 긴 증가하는 부분 수열 (JAVA)

문제

풀이

O(n^2)의 복잡도로 풀 수 있는 문제다.

• arr[]: 주어진 배열 값
• dp[i]: arr[i]를 수열의 마지막으로 할 때의 가장 긴 증가하는 수열의 길이

1. 현재 arr[i]보다 앞의 arr[j]값이 작은 경우에만 증가하는 수열에 arr[i]를 추가할 수 있으므로, 앞의 dp[j]값들 중 최댓값을 찾아 max에 저장한다.
2. 만약 arr[i] 값이 앞선 모든 값들보다 큰 경우, 새로운 증가하는 수열을 만든다는 의미로 0을 저장한다.
3. 이렇게 배열의 모든 값을 순회한 후, dp[]의 최댓값을 찾으면 정답이다. arr[n]이 증가하는 수열의 끝이라고 보장할 수 없으므로 최댓값을 따로 찾아서 리턴해야 한다.

코드

import java.io.*;

public class Main {

    private static final int MAXIMUM = 1000;

    private static int n;
    private static int[] arr = new int[MAXIMUM + 1];
    private static int[] dp = new int[MAXIMUM + 1];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        n = Integer.parseInt(br.readLine());
        String[] line = br.readLine().split(" ");
        for (int i = 1; i <= n; i++) arr[i] = Integer.parseInt(line[i - 1]);

        dp();
        bw.append(String.valueOf(getMax()));

        br.close();
        bw.close();
    }

    private static void dp() {
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            int max = 0;
            for (int j = i - 1; j >= 1; j--)
                if (arr[i] > arr[j]) max = Math.max(max, dp[j]);
            dp[i] = max + 1;
        }
    }

    private static int getMax() {
        int max = 0;
        for (int val : dp) max = Math.max(max, val);
        return max;
    }
}