11053. 가장 긴 증가하는 부분 수열

11053. 가장 긴 증가하는 부분 수열

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

---

유명한 문제이다. (알고스팟에도 있는 문제다. https://algospot.com/judge/problem/read/LIS)

일명 Longest Increasing Sequence 라는 문제인데, 주어진 수열에서 가장 긴 길이를 가질 수 있는 증가하는 부분 수열의 길이를 리턴해야 한다. 

가장 먼저 1로 (가질 수 있는 최소 길이값이 길이1이므로) 값을 초기화 한 dp를 선언하고, i는 1부터 길이까지 증가시키고 j는 0부터 i까지 증가 시켜서, i번째 값이 j번째 값 보다 크면 dp[j] + 1이나 현재 값 dp[i] 중 maximum 값으로 갱신하는 것이다.

동영상 설명이 잘 되어 있어서 링크를 건다. https://www.youtube.com/watch?v=CE2b_-XfVDk

import java.util.Scanner;

public class Main {

    public int problem11053(int[] arr) {
        int[] dp = new int[arr.length];

        for (int i = 0; i < arr.length; ++i) {
            dp[i] = 1;
        }

        for (int i = 1; i < arr.length; ++i) {
            for (int j = 0; j < i; ++j) {
                if (arr[i] > arr[j]) {
                    dp[i] = Math.max(dp[j] + 1, dp[i]);
                }
            }
        }
        int res = 1;
        for (int i = 0; i < arr.length; ++i) {
            res = Math.max(res, dp[i]);
        }
        return res;
    }

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

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; ++i) {
            arr[i] = sc.nextInt();
        }
        System.out.println(main.problem11053(arr));
    }
}