300. Longest Increasing Subsequence

Source link: https://leetcode.com/problems/longest-increasing-subsequence/

Design

Method I (Dynamic Programming)

  1. Initialize an array dp for storing the increasing subsequence length for each element inside the array nums, and a variable maxLen for recording the max length of the increasing subsequence to the current element.
  2. Traverse through the array nums, for each one, traverse its previous elements. If the previous element is smaller than the current element, update the increasing subsequence length and store it into the array dp.
  3. If the variable maxLen is smaller than the longest increasing subsequence length so far, update it.
  4. Return maxLen until the end of the loop.
Longest Increasing Subsequence

Method II (Binary Search)

English version: https://leetcode.com/problems/longest-increasing-subsequence/discuss/74824/JavaPython-Binary-search-O(nlogn)-time-with-explanation

Chinese version: https://segmentfault.com/a/1190000003819886

Implementation

Method I

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

Method II

class Solution {
  public int lengthOfLIS(int[] nums) {
    int[] tails = new int[nums.length];
    int len = 0;
    for (int num : nums) {
        int left = 0, right = len;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (tails[mid] < num)
                left = mid + 1;
            else
                right = mid;
        }
        tails[left] = num;
        if (left == len) ++len;
    }
    return len;
    }
}

Complexity Analysis

Method I

Time: $O(n^2)$

Space: $O(n)$

Method II

Time: $O(nlogn)$

Space: $O(n)$