[백준 11722] 가장 긴 감소하는 부분 수열

 

이중 루프로 인덱스를 비교한다.

 

i	10	30	10	20	20	10
j	10	30	10	20	20	10
dp	1	1	2	2

다음을 만족할때 수열의 길이가 1 증가한다.

1. i 가 j 보다 작을 때

2. dp[i] 보다 dp[j] + 1 이 클 때

 

2번 조건을 만족하지 않으면 앞의 인덱스 중 자신보다 큰 수가 있으면 길이가 무조건 1 증가한다.

 

수열의 길이는 최소 1이므로 dp 배열의 초기값은 1이다.

 

 

public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        int a[] = new int[n];
        int dp[] = new int[n];
        
        for(int i=0; i<n; i++)
            a[i] = sc.nextInt();
        
        int max = 0;
        for(int i=0; i<n; i++) {
            dp[i] = 1;
            for(int j=0; j<i; j++) {
                if(a[i] < a[j] && dp[j] + 1 > dp[i])
                    dp[i] = dp[j] + 1;
                if(max < dp[i])
                	max = dp[i];
            }
        }
        
        System.out.println(max);
        sc.close();
}