[백준 11053번 : 가장 긴 증가하는 부분 수열] java 풀이

발그림으로 설명해봤당

n번째 인덱스까지의 가장 긴 수열을 구한다고 했을 때 n-1번째까지를 따져야한다.

만약 n번째 숫자가 0번째~n-1번째 까지 순환한다고 하면 순환하는 각 숫자는 i번째 인덱스라고 지칭한다. 각 i번째 숫자보다 n번째 숫자가 클 경우 해당 숫자의 dp값(수열 길이)+1(n번째가 추가된다고 가정하므로) 보다 n번째 숫자가 가지고 있는 dp[n]값보다 크면 그걸 선택하도록 한다.

여기서 재귀 방식을 선택했으므로 dp[i]=seq(i)가 되는 것이다.

🔑 java 풀이

-import java.util.Scanner;

public class Main {
    static int arr[];
    static int dp[];

    public static int seq(int n){
        if(dp[n]==-1){
            dp[n]=1;

            for(int i=0; i<n; i++){
                if(arr[n]>arr[i]){
                    dp[n]=Math.max(dp[n],seq(i)+1);
                }
            }
        }
        return dp[n];
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        dp = new int[n];
        for(int i=0; i<n; i++)
            dp[i]=-1;

        dp[0]=1;

        for(int i=0; i<n; i++){
            seq(i);
        }

        int max=0;
        for(int i=0; i<n; i++){
            if(max<dp[i])
                max=dp[i];
        }
        System.out.println(max);
    }
}