[프로그래머스] LIS

 

/* LIS 최장 증가 부분 수열 */

LIS란?

 

최장 증가 부분 수열(Longest Increasing Subsequence, LIS)은 주어진 수열에서 순서를 유지하면서 가장 긴 증가하는 부분 수열을 찾는 문제입니다.

 

/* 1. DP 방식 O(N^2)*/

import java.util.*;

public class LIS_DP {
    public static int lis(int[] arr) {
        int n = arr.length;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);

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

        int maxLIS = 0;
        for (int length : dp) {
            maxLIS = Math.max(maxLIS, length);
        }
        return maxLIS;
    }

    public static void main(String[] args) {
        int[] arr = {10, 20, 10, 30, 20, 50};
        System.out.println(lis(arr)); // 출력: 4
    }
}

 

/* 2. DP  + 이분탐색 O(N Log N)*/

import java.util.*;

public class LIS_BinarySearch {
    // 이진 탐색 직접 구현 (lower bound 찾기)
    private static int binarySearch(List<Integer> lis, int target) {
        int left = 0, right = lis.size() - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (lis.get(mid) >= target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    public static int lis(int[] arr) {
        List<Integer> lis = new ArrayList<>();

        for (int num : arr) {
            int pos = binarySearch(lis, num);
            if (pos == lis.size()) {
                lis.add(num);
            } else {
                lis.set(pos, num);
            }
        }
        return lis.size();
    }

    public static void main(String[] args) {
        int[] arr = {10, 20, 10, 30, 20, 50};
        System.out.println(lis(arr)); // 출력: 4
    }
}