[Algorithm] Leetcode_Longest Increasing Subsequence

JAsmine_log·2024년 4월 2일

Problems

Given an integer array nums, return the length of the longest strictly increasing subsequence.

Example 1:

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Example 2:

Input: nums = [0,1,0,3,2,3]
Output: 4
Example 3:

Input: nums = [7,7,7,7,7,7,7]
Output: 1

Constraints:

1 <= nums.length <= 2500
-104 <= nums[i] <= 104

Follow up:

Can you come up with an algorithm that runs in O(n log(n)) time complexity?

Analysis & Solutions

base case : nums.len을 모두 순회하면 끝
if (pivot < nums[index]) : pivot과 count 업데이트
recursive(nums[index], index+1, count++)
else (pivot >=nums[index]): pivot과 count 업데이트 없음
recursive(pivot, index+1, count)

Tip
이 문제의 핵심은 조건에 따라 선택할지 말지를 결정하는 것이다.
그래서 Take는 조건에 맞는 경우에 선택하고,
그렇지 않은 경우에는 notTake한다.
그리고 둘 중에 더 큰 값을 가져다가 쓰는 것이다.

Code : Recursion

Geeks for Geeks 참고해서 풀었는데, Time limit 났다.
이 문제는 친구가 전형적인 recursion이라고 추천해서 풀어본 것인데, 그래도 Recursion으로 풀기위해 계속 해봐야겠다.

1st Trial

class Solution {

    static int max_ref;
     
    static int _lis(int arr[], int n){
        // Base case
        if (n == 1)
            return 1;
      
        int res, max_ending_here = 1;
 
        for (int i = 1; i < n; i++){
            res = _lis(arr, i);
            if (arr[i - 1] < arr[n - 1] && res + 1 > max_ending_here)
                max_ending_here = res + 1;
        }

        if (max_ref < max_ending_here)
            max_ref = max_ending_here;
            
        return max_ending_here;
    }

    static int lis(int arr[], int n){  
        max_ref = 1;       
        _lis(arr, n);
        return max_ref;
    }

    public int lengthOfLIS(int[] nums) {
       
        return lis(nums, nums.length);

    }
}

2nd Trial..
이렇게하면 Time-limit 이 나는데, 이를 보완하기 위해서 Memoization을 이용해야한다.


public class Solution{
	//prev index : -1, 0, 1, 2, ..., n-1
 	//cur index   : 0, 1, 2,3 , ..., n

    private int[] nums = null;

    public int lengthOfLIS(int[] nums) {
        this.nums = nums;
        return recursion(-1, 0);
    }

    private int recursion(int prevIndex, int curIndex) {

        //base case:
        if (curIndex >= nums.length){
            return 0;
        }

        int take = 0;
        if (prevIndex == -1 || nums[curIndex] > nums[prevIndex]) {
            //Take
            take = 1 + recursion(curIndex, curIndex + 1);
        }
        //notTake
        int notTake=0;
        notTake= recursion(prevIndex, curIndex + 1);

        return Math.max(take, notTake);
    }
}

Code : Memoization

위에서, Recursion만 사용하는 다양한 시도를 해 보았는데 에러가 나서 Memoization을 적용한다.

public class Solution {
    private int[] nums = null;
    private Memo memo = null;

    public int lengthOfLIS(int[] nums) {
        this.nums = nums;
        this.memo = new Memo(nums.length + 1, nums.length + 1);

        return recursion(null, 0);
    }

    // NOTE: pivot 이 아직 선택되지 않은 경우 pivotIndex 를 null 로 한다.
    private int recursion(Integer pivotIndex, int index) {
        if (this.memo.contains(pivotIndex, index)) {
            return this.memo.get(pivotIndex, index);
        }

        if (this.nums.length == index) return 0;

        int result;
        if (pivotIndex == null || this.nums[pivotIndex] < this.nums[index]) {
            result = Math.max(
                    recursion(index, index + 1) + 1,
                    recursion(pivotIndex, index + 1)
            );
        } else {
            result = recursion(pivotIndex, index + 1);
        }

        return this.memo.setAndGet(pivotIndex, index, result);
    }

    static class Memo {
        private final int EMPTY = -1;
        private final int[][] memo;

        Memo(int size1, int size2) {
            this.memo = new int[size1][size2];
            for (int[] l : this.memo) Arrays.fill(l, EMPTY);
        }

        boolean contains(Integer i, int j) {
            if (i == null) return false;
            return this.memo[i][j] != EMPTY;
        }

        int get(Integer i, int j) {
            return this.memo[i][j];
        }

        int setAndGet(Integer i, int j, int value) {
            if (i == null) return value;
            return this.memo[i][j] = value;
        }

Code : Dynamic Programming

public class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);
        int max = 1;
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
                max = Math.max(max, dp[i]);
            }
        }
        return max;
    }
}