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;
    }
}