백준 JAVA 11722번 가장 긴 감소하는 부분 수열

문제 링크: https://www.acmicpc.net/problem/11722

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

 

 

해당 문제를 처음에는 DFS로 시도했지만 시간초과로 실패했다. 그래서 DP로 다시 풀어 보았다.

 

 

import java.math.BigInteger;
import java.util.*;
import java.io.*;



public class Main {


    static int [] arr;
    static int t;
    public static void main(String [] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        t= Integer.parseInt(br.readLine());
        arr = new int [t+1];

        String[] s = br.readLine().split(" ");

        for(int i=0; i<t; i++){
            arr[i+1]=Integer.parseInt(s[i]);
        }


        int d[] = new int[t + 1];
        d[1] = 1;

        for (int i = 2; i <= t; i++) {
            d[i] = 1;
            for (int j = 1; j < i; j++) {
                if (arr[i] < arr[j] && d[i] <= d[j]) {
                    d[i] = d[j] + 1;
                } else if (arr[i] == arr[j]) {
                    d[i] = d[j];
                }
            }
        }
        int max = 0;
        for (int i = 1; i <= t; i++)
            max = Math.max(d[i], max);
        System.out.println(max);
    }


}