300. Longest Increasing Subsequence

[LLancelot]

题目 Given an unsorted array of integers, find the length of longest increasing subsequence.

Example:

Input: [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.

二分查找 (nlogn)

• 推荐写法 Java版：

  class Solution {
  public int lengthOfLIS(int[] nums) {
      int n = nums.length;
      int[] q = new int[n + 1];
      int len = 0;
      for (int i = 0; i < n; i++) {
          int left = 0, right = len;
          while (left < right) {
              int mid = left + right + 1 >> 1;
              if (q[mid] >= nums[i]) right = mid - 1;
              else left = mid;
          }
          len = Math.max(len, right + 1);
          q[right + 1] = nums[i];
      }
      return len;
  }

• 推荐写法 Python版：

  class Solution(object):
  def lengthOfLIS(self, arr):
      """
      :type nums: List[int]
      :rtype: int
      """
      tails = [0] * len(arr)
      size = 0
      for x in arr:
          left, right = 0, size
          while left != right:
              mid = (left + right) / 2
              if tails[mid] < x:
                  left = mid + 1
              else:
                  right = mid
          tails[left] = x
  
          size = max(size, left + 1)
      return size

  或者

  class Solution:
  def lengthOfLIS(self, nums: List[int]) -> int:
      from bisect import bisect_left
      dp = []
      for num in nums:
          i = bisect_left(dp, num)
          if i == len(dp):
              dp.append(num)
          else:
              dp[i] = num
  
      return len(dp)

动态规划 (n^2)，不推荐

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