[LeetCode] Longest Increasing Subsequence (Java)

✉️문제

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

Longest Increasing Subsequence - LeetCode

 

📝 접근

1. 다이나믹 프로그래밍을 이용한 방법 

 - D[i] = i번 째에서 구할 수 있는 가장 긴 수열

 - 시간 복잡도 : O(N^2)

2. 그리디와 이진 탐색을 이용한 방법

 - 시간 복잡도 : O(n log n)

 

🗝 문제풀이

1. 다이나믹 프로그래밍

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 res = Integer.MIN_VALUE;
    for(int n : dp) {
        res = Math.max(n, res);
    }

    return res;
}

 

2. 그리디와 이진탐색

public int lengthOfLIS2(int[] nums) {
    ArrayList<Integer> res = new ArrayList<>();
    for(int i = 0; i < nums.length; i++) {
        if(res.isEmpty() || nums[i] > res.get(res.size() - 1)) {
            res.add(nums[i]);
        } else {
            searchRightPlace(res, nums[i]);
        }
    }

    return res.size();
}

private void searchRightPlace(ArrayList<Integer> res, int num) {
    int l = 0;
    int r = res.size() - 1;
    while(l < r) {
        int mid =  (l + r) / 2;
        if (num > res.get(mid)) {
            l = mid + 1;
        } else {
            r = mid;
        }
    }
    res.set(l, num);
}