최대 부분 증가수열(LIS)

!다시 풀어보기

 

N개의 자연수로 이루어진 수열이 주어졌을 때, 그 중에서 가장 길게 증가하는(작은 수에서 큰 수로) 원소들의 집합을 찾는 프로그램을 작성하라.

예를 들어, 원소가 2, 7, 5, 8, 6, 4, 7, 12, 3 이면 가장 길게 증가하도록 원소들을 차례대로 뽑아내면 2, 5, 6, 7, 12를 뽑아내어

길이가 5인 최대 부분 증가수열을 만들 수 있다.

 

입력

8
5 3 7 8 6 2 9 4

출력

4

 

부분증가수열, 원소들의 숫자는 유지해야함

dy[i] = 마지막 숫자를 arr[i]로 하는 부분증가수열의 최대 길이

arr[0]의 dy[i]는 맨 앞이므로 1,

그 뒤에 원소들은 arr[i] 앞 인덱스의 원소들을 반복문으로 돌면서 앞에 원소가 arr[i] 보다 작고, dy[앞에원소]가 0보다 크면 dy[해당원소] = dy[앞에원소]중 최대값에 +1을 해준다

 

import java.util.*;

class Main{

    static int[] dy;
    public int Solution(int[] arr){
       int ans = 0;
       dy = new int[arr.length];
       dy[0] = 1; //맨 앞 인덱스는 자기자신만 증가수열의 원소, 직관적으로 1
       for (int i = 1; i < arr.length; i++){
            int max = 0; // max를 0으로 둬야 앞에 큰 원소가 없을때 dy[i] 값을 1로 저장 가능
            for (int j = i-1; j >= 0; j--){
                //앞의 항이 될 수 있는 arr[j] 중 dy[j]의 값이 0보다 클때 값을 저장
                if (arr[j] < arr[i] && dy[j] > max) max = dy[j];
            }
            //i보다 작은 인덱스에서 지금까지의 최대값 + 1이 dy[i]번째의 값
            dy[i] = max+1;
           ans = Math.max(ans,dy[i]);
       }
        return ans;
    }

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