Daily LeetCode 300. Longest Increasing Subsequence

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

Medium

问题描述

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. 

Note:

• There may be more than one LIS combination, it is only necessary for you to return the length.
• Your algorithm should run in O(n2) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

思路及代码

这一题要求最长升序子串的长度。

我们可以维护一个一维数组dp，dp[i]表示Input[0:i]中最长升序子串的长度，对于每一个Input[0:i-1]，我们在这个子串中寻找是否存在小于Input[i]的数Input[j]，如果找到了，则说明当前Input[i]可以作为Input[j]的升序子串的下一个数，我们就可以更新dp数组：dp[i]=max(dp[j] + 1, dp[i])，最终返回dp数组中的最大值，即最长升序子串的长度。

代码：

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if len(nums) == 0: return 0
        dp = [1] * (len(nums))
        for i in range(1, len(nums)):
            for j in range(i):
                if nums[j] < nums[i]:
                    dp[i] = max(dp[j] + 1, dp[i])

        return max(dp)  

下面是从论坛看到的时间复杂度为O(nlogn)的解法：

维护一个tails数组，保存所有升序子串中最小的“尾元素”，长度为i+1的子串的tail保存在tails[i]中。

假设给定数组[4, 5, 6, 3]：

len = 1   :      [4], [5], [6], [3]   => tails[0] = 3
len = 2   :      [4, 5], [5, 6]       => tails[1] = 5
len = 3   :      [4, 5, 6]            => tails[2] = 6

我们可以看出，tails数组肯定是一个升序数组，因此我们可以二分查找tails数组，找出需要更新的项：

(1) if x is larger than all tails, append it, increase the size by 1
(2) if tails[i-1] < x <= tails[i], update tails[i]

代码如下：

def lengthOfLIS(self, nums):
    tails = [0] * len(nums)
    size = 0
    for x in nums:
        i, j = 0, size
        while i != j:
            m = (i + j) / 2
            if tails[m] < x:
                i = m + 1
            else:
                j = m
        tails[i] = x
        size = max(i + 1, size)
    return size