LIS Longest Increasing Sequence / ALGOSPOT

문제링크 : https://algospot.com/judge/problem/read/LIS
제출링크 : https://algospot.com/judge/submission/detail/655189
자바소스 : https://github.com/skysign/WSAPT/blob/master/ALGOSPOT/LIS/src/Main.java

이 문제는 1차원 DP 문제로, O(N^2)로 풀수 있는 문제입니다.
아래의 LIS()메서드를 참고하세요.

문제 푸는 것 보다, 책의 코드 8.12 li3()함수를 이해하는 것이 더 어려웠던 문제입니다.
보시는 분들의 이해를 돕기 위해서, lis3() 함수를 자바 버전으로 구현해 봤습니다.
(코드 8.12에서 사용된 변수명과 아래 메서드에서 사용된 변수명이 같다면, 역할이 동일합니다.)

    public int lis3(int start) {
        if(cache[start+1] != 0)
            return cache[start+1];

        int r = 1;
        cache[start+1] = r;

        for(int next=start+1; next<n; ++next) {
            if((start == -1) || (S[start] < S[next])) {
                r = Math.max(r, lis3(next)+1);
                cache[start+1] = r;
            }
        }

        return r;
    }

아래의 루프 1개를 가지고, 2가지 목적으로 사용하는 것이 lis2()와 lis3()의 주된 차이점입니다.
for(int next=start+1; next<n; ++next)

1. 0 부터 N까지 한번씩 lis3()를 호출 한다.
2. S[start] < S[next] 가 true면 lis3(next+1)을 호출 한다.

위의 메서드가 start는 -1인 상태로 호출되는 것이 포인트 입니다.
따라서, 첫번째 루프가 start가 -1인 상태로 위의 #1을 실행하는 목적이구요,
두번째 루프, 즉 start가 0 부터 호출되는 루프는 위의 #2를 실행하는 목적입니다.
이렇게 루프가 실행되면서, 중복해서 lis3()가 호출 될 것 같지만,
cache를 사용해서, 한번 방문한 곳은 중복해서 방문하지 않기 때문에, 중복된 lis3() 호출은 발생하지 않습니다.

import java.util.Scanner;

/**
 * LIS Longest Increasing Sequence / ALGOSPOT
 * 문제링크 : https://algospot.com/judge/problem/read/LIS
 * 제출링크 : https://algospot.com/judge/submission/detail/655189
 */
public class Main {
    Scanner sc = new Scanner(System.in);
    int[] cache;
    int n = 0;
    int[] S;

    public void solve() {
        int T = sc.nextInt();
        int r = 0;

        for(int t=0; t<T; ++t) {
            int N = sc.nextInt();
            n = N;
            S = new int[N];

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

//            r = LIS(S, N);
//            System.out.println(r);

            cache = new int[N+1];
            r = lis3(-1);
            System.out.println(r-1);
        }
    }

    public int LIS(int[] map, int N) {
        int[] dp = new int[N+1];

        for(int i=0; i<N; ++i) {
            int max = 1;
            for(int k=0; k<i; ++k) {
                if(map[k] < map[i])
                    max = Math.max(max, dp[k]+1);
            }
            dp[i] = max;
        }

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

        return r;
    }

    /**
     * 책 234페이지, 코드 8.12를 자바버전으로 구현한 메서드 입니다.
     * 코드 보시는 분들이 헷갈리지 않도록, ret를 제외하고는, 코드 8.12에서 사용된
     * 변수명과 아래 메서드에서 사용된 변수명이 같다면, 역할도 동일합니다.
     * @param start
     * @return
     */
    public int lis3(int start) {
        if(cache[start+1] != 0)
            return cache[start+1];

        int r = 1;
        cache[start+1] = r;

        for(int next=start+1; next<n; ++next) {
            if((start == -1) || (S[start] < S[next])) {
                r = Math.max(r, lis3(next)+1);
                cache[start+1] = r;
            }
        }

        return r;
    }

    public static void main(String[] args) {
        Main main = new Main();
        main.solve();
    }
}