최대부분증가수열(LIS)

 

원소가 n개인 배열의 일부 원소를 골라내서 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고, 그 길이가 최대인 부분 수열을 최장 증가 부분 수열(Longest Increasing Subsequence)이라고 한다.

 

dy[i]는 i 번째 숫자를 마지막 항으로 하는 최대 증가 수열의 길이를 저장할 배열임

dy[0]은 5를 마지막 항으로 하는 최장 길이 = 1 (5 하나 밖에 없으니)

dy[1]은 3을 마지막 항으로 하는 최장 길이 = 1 (5보다 3이 작으니 3만)

dy[2]은 7을 마지막 항으로 하는 최장 길이 = 2 (3과 5 둘 다 가능 3 7 or 5 7 둘의 길이가 같으니 아무거나)

dy[3]은 8을 마지막 항으로 하는 최장 길이 = 3 (3과 5와 7 셋 다 가능 근데 7을 마지막 항으로 하는게 크니 그거 선택)

 

import java.util.*;
class Main{
    static int[] dy;

    public int solution(int[] arr){
        int answer=0;
        //dy[i]는 i를 마지막 항으로 하는 최대 증가 수열의 길이
        dy= new int[arr.length];
        
        //숫자 하나만 가지고 수열을 만드는 경우는 길이가 1임
        dy[0] = 1;
        
        //각 배열의 숫자들에 대해 최대 증가 수열의 길이를 구한다.
        for(int i = 1; i < arr.length; i++) {
            int max = 0;
            //이전 항 들의 최대 증가 수열의 길이를 탐색
            for(int j = i-1; j >= 0; j--) {
                //증가 수열을 만들 수 있는 것 중의 길이가 최대인 것을 max로 둔다.
                //이전 항이 더 작아야 만들 수 있음
                if(arr[j] < arr[i] && dy[j] > max) max = dy[j];
            }
            dy[i] = max + 1;
            answer = Math.max(answer, dy[i]);
        }
        return answer;
    }

    public static void main(String[] args){
        Main T = new Main();
        Scanner kb = new Scanner(System.in);
        int n=kb.nextInt();
        int[] arr=new int[n];
        for(int i=0; i<n; i++){
            arr[i]=kb.nextInt();
        }
        System.out.print(T.solution(arr));
    }
}