(DP, Medium) Longest Increasing Subsequence

https://leetcode.com/problems/longest-increasing-subsequence/description/

문제에서 O(n log n)으로 풀어보라는 챌린지가 있는데 바로 떠오르진 않고..
O(n^2)는 다음과 같이 할 수 있겠다.

nums길이와 똑같은 배열을 만들어서 1로 초기화한다(자기 자신 포함 길이기 때문에 최소 1).

1부터 순회하며 이전 인덱스들에서 현재 인덱스보다 작은 값이 있는 경우 경우의 수 누적
이 때 발견된 직전 인덱스에서 한 칸 (+1) 한 값보다 현재 세팅값이 클 수 있으므로 Math.max 사용

class Solution {
    public int lengthOfLIS(int[] nums) {

        int[] dp = new int[nums.length];
        // 자신을 포함하므로 기본적으로 모두 1
        Arrays.fill(dp, 1);

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

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

솔루션 참고해서 O(n log n)풀이도 찾았다.
이분탐색을 사용해서 애초에 정렬된 ArrayList를 만드는 솔루션이다.

class Solution {
    public int lengthOfLIS(int[] nums) {
        List<Integer> res = new ArrayList<>();

        for (int n : nums) {
            if (res.isEmpty() || res.get(res.size() - 1) < n) {
                res.add(n);
            } else {
                int idx = binarySearch(res, n);
                res.set(idx, n);
            }
        }

        return res.size();        
    }

    private int binarySearch(List<Integer> arr, int target) {
        int left = 0;
        int right = arr.size() - 1;

        while (left <= right) {
            int mid = (left + right) / 2;
            if (arr.get(mid) == target) {
                return mid;
            } else if (arr.get(mid) > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }    
}

for문의 한 번 순회마다 res를 찍어보면 다음과 같다.

[10]
[9]
[2]
[2, 5]
[2, 3]
[2, 3, 7]
[2, 3, 7, 101]
[2, 3, 7, 18]