LIS 가장 긴 증가하는 부분 수열 ( 백준 11053 )

https://www.acmicpc.net/problem/11053

 

* 배열 중 증가하는 배열을 찾아서 제일 긴 길이를 반환하면 됨

* 혼자 생각이 떠오르지 않아서 답을 참고해서 해결

* dp 배열을 사용하여 증가 수열 일때마다 최대값으로 갱신

 

* 각 원소는 길이 1이라는 값을 기본으로 갖고 있으므로 dp 배열을 전부 1로 초기화 시켜줌

* 2중 for 루프를 돌면서 포인터 i와j가 증가하는 수열을 탐색함

* 그림과 같이 첫 for 루프를 돌릴때 예시인데 j가 10을 가르키고 i가 20을 가르키면 증가하는 수열로 간주함

* j포인터에서 길이 1 증가하니까 dp[j]+1과 dp[i]의 최댓값을 비교하여 dp[i]에 길이값을 갱신

* 배열 길이만큼 반복하면 끝

 

import java.io.*;
import java.util.*;

public class BOJ11053 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int size = Integer.parseInt(br.readLine());
        int[] arr = new int[size];
        int[] dp = new int[size];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < size; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.fill(dp, 1);

        for(int i = 1; i < size; i++) {
            for(int j = 0; j < i; j++) {
                if(arr[i] > arr[j]) {
                    dp[i] = Math.max(dp[j]+1, dp[i]);
                }
            }
        }
        int max = Integer.MIN_VALUE;
        for(int i = 0; i < size; i++) {
            max = Math.max(max, dp[i]);
        }
        System.out.print(max);
    }
}

 

* 마지막에 dp 배열의 최댓값을 출력하면 증가 수열의 최대값이므로 답.