11053. 가장 긴 증가하는 부분 수열(Java)

문제 링크

https://www.acmicpc.net/problem/11053

11053번: 가장 긴 증가하는 부분 수열

 

문제 풀이

DP 문제입니다. n의 범위를 고려해서 이중 for문을 사용했습니다.

 

코드

package jason.baekjoon.problem11053;

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int answer=1;

        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();
            dp[i] = 1;
        }

        for(int i=1;i<n;i++){

            for(int j=0;j<i;j++){
                if(A[j]<A[i]){
                    dp[i]=Math.max(dp[i], dp[j]+1);
                }
            }
            answer=Math.max(answer, dp[i]);
        }


        System.out.println(answer);
    }
}