백준 Java | 백준 11722번 가장 긴 감소하는 부분 수열 Java 문제 풀이

11722번: 가장 긴 감소하는 부분 수열 (acmicpc.net)

11722번: 가장 긴 감소하는 부분 수열

 

DP[i] = A[i]를 마지막 값으로 가지는 가장 긴 감소 부분 수열의 길이로 정의하면 쉽게 풀 수 있다. 

O(N^2) 알고리즘

import java.util.*;

class Main {
    static int n;
    static int[] A;
    static int[] DP;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();

        A = new int[n];
        DP = new int[n];
        for (int i=0;i<n;i++){
            A[i] = sc.nextInt();
        }

        int answer = solution();
        System.out.println(answer);
    }

    private static int solution() {
        int max = 1;
        for (int i=0;i<n;i++){
            int tmp = 1;
            for (int j=0;j<i;j++){
                if (A[j] > A[i]){
                    tmp = Math.max(DP[j]+1, tmp);
                }
            }
            DP[i] = tmp;
            max = Math.max(DP[i], max);
        }
        return max;
    }
}