300. (LIS)Longest Increasing Subsequence

tags: fundamental

ChungYi

  • Solution 1 Recursive + Memorization =DP O(n^2)

  • Explanation

    F([1..n]) = Max{ lengthOfLISEndOfTail(i) for i= 1..n}

    lengthOfLISEndOfTail(i) = max( lengthOfLISEndOfTail( j ) for j= 1..i if nums[i] > nums[j] else 0, 1)

    DP for lengthOfLISEndOfTail(i)

  • performance o(n^2)

    • Complexity: o(n^2)
    • Performance
      • time: 65%
      • memeory 34%

  • code

    class Solution {

    private int[] table;

    public int lengthOfLIS(int[] nums) {
        int res = 0;
        this.table = new int[nums.length];
        for (int idx = 0; idx < nums.length; idx++)
            this.table[idx] = -1;

        for (int idx = 0; idx < nums.length; idx++) {
            res = Math.max(lengthOfLISEndOfTail(nums, idx), res);
        }

        return res;
    }

    public int lengthOfLISEndOfTail(int[] nums, int tail) {

        if (tail == 0)
            return 1;

        if (this.table[tail] != -1)
            return this.table[tail];

        int res = 1;
        for (int idx = 0; idx < tail; idx++) {
            if (nums[tail] > nums[idx]) {
                res = Math.max(lengthOfLISEndOfTail(nums, idx) + 1, res);
            }
        }
        this.table[tail] = res;
        return res;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.lengthOfLIS(new int[] { 10, 9, 2, 5, 3, 7, 101, 18 }));
    }
}

ChungYi (Robinson-Schensted-Knuth)

  • Solution 2 RSK algorithm (Robinson-Schensted-Knuth)

    • Explanation

      • Greedy algorithm

  • performance O( n*lon(n) )

    • Performance
      • time: 92%
      • memeory 34%

  • code

import java.util.ArrayList;
import java.util.Collections;

class Solution {
    public int lengthOfLIS(int[] nums) {
        return RSK_LIS(nums);
    }

    public int RSK_LIS(int[] nums) {
        ArrayList<Integer> aryList = new ArrayList<Integer>();

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

        aryList.add(nums[0]);
        for (int idx = 1; idx < nums.length; idx++) {
            if (nums[idx] > aryList.get(aryList.size() - 1)) {
                aryList.add(nums[idx]);
            } else {
                int findPoint = Collections.binarySearch(aryList, nums[idx]);
                if (findPoint >= 0)
                    continue;

                int insertPoint = (-1) * (findPoint + 1);
                aryList.set(insertPoint, nums[idx]);
            }

        }

        return aryList.size();

    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.lengthOfLIS(new int[] { 2, 2 }));
    }
}

Hannah

Approach 3: Dynamic Programming
























import java.util.Arrays;
class Solution {
    public int lengthOfLIS(int[] nums) {
        int len = nums.length;
        if(len==0){
            return 0;
        }
        int[] memo = new int[len];
    
        for(int i=0; i<len; i++){
            int max = 1;
            for(int j=0; j<i+1; j++){
                if(nums[i]>nums[j] && memo[j]+1 > max){
                    max=memo[j]+1;
                }
            }
            memo[i]=max;
            // System.out.println(Arrays.toString(memo));
        }

        return Arrays.stream(memo).max().getAsInt();
    }
}
Select a repo