Longest Increasing Subsequence / geeksforgeeks.org

어떤 리스트가 있다고 할 때, 그 리스트에서, 값이 상승하는 순서로, 가장 긴 리스트를 찾는 문제입니다.

5 8 3 7 9 1 이 주어졌다고 하면,

5, 7, 9 이렇게 3이 Longest Increasing Subsequence 가 됩니다.

Box stacking문제를 풀기전에 미리 풀어 봤더라면, 좋았을 문제입니다. DP의 Memoization을 공부할 수 있는 좋은 문제입니다.

Longest Increasing Subsequence 문제 링크
Longest Increasing Subsequence 문제 해설
문제 푼 자바 소스

 import java.util.Scanner;

public class GFG {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();

        while(T-->0) {
            int N = sc.nextInt();
            int[] a = new int[N];

            for(int i=0; i<N; ++i) {
                a[i] = sc.nextInt();
            }

            int r = LIS(a, N);
            System.out.println(r);
        }
    }

    public static int LIS(int[] a, int N) {
        int[] lis = new int[N];

        for(int i=0; i<N; ++i) {
            lis[i] = 1;
            int maxLisLTi = 0;
            for(int j=0; j<i; ++j) {
                if(a[j] < a[i]) {
                    maxLisLTi = Math.max(maxLisLTi, lis[j]);
                }
            }

            lis[i] += maxLisLTi;
        }

        int r = lis[0];
        for(int i=0; i<N; ++i)
            r = Math.max(r, lis[i]);

        return r;
    }
}