[JAVA] 백준 다이나믹 프로그래밍 연습문제 - BOJ 11053

주어진 수열 내에서 증가하는 부분수열 LIS 중 최대길이를 구하기

 

- 주어진 수열 a[]와 수열의 i번째 수까지의 LIS 최대길이를 저장하는 d[]를 생성

- 부분수열이 존재하지 않을 때의 기본값인 1로 d[]를 초기화함

- 2부터 수열의 길이 n까지 반복하여 d[]에 값을 저장한다.

 

- 인덱스 i 이하인 수 j 중에서 a[i]보다 크면서, d[i]-1보다 큰 d[j]를 찾으면 d[i]=d[j]+1 로 업데이트한다.

- 저장된 d[] 에서 최대값이 존재하는 LIS의 최대길이이다.

 

import java.util.Scanner;

public class BOJ11053 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int a[] = new int[n + 1];
        int d[] = new int[n + 1];
        int ans=d[1];

        for (int i = 1; i <= n; i++) {
            a[i] = sc.nextInt();
            d[i] = 1;
        }

        for (int i = 2; i <= n; i++) {
            for (int j = i - 1; j >= 1; j--) {
                if (a[i] > a[j] && d[i] < d[j] + 1) {
                    d[i] = d[j] + 1;
                }
            }
        }
        for(int i=1;i<=n;i++){
            if(ans<d[i])
                ans=d[i];
        }
        System.out.println(ans);

    }
}