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

 

가장 긴 감소하는 부분 수열을 먼저 풀고 풀었다.

수열의 수에 대한 크기 비교만 거꾸로 하면 된다.

 

 

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();
}