Leetcode-300. 最长上升子序列

给定一个无序的整数数组，找到其中最长上升子序列的长度。

示例:

输入: [10,9,2,5,3,7,101,18]
输出: 4 
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

说明:

• 可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
• 你算法的时间复杂度应该为 O(n2) 。
• 进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?

解法：1.DP法。这里给出的dp[i]的含义是从头到i（必须包含i）的最长子序列的长度，定义j是小于i的索引，范围在0-i，则状态转移方程就是当nums[i]>nums[j]时，dp[i] = max{ dp[j]+1 }，选出所有自序列中最长的上升子序列，最终的最长子序列是所有dp[i]中最大的，而并非是dp[n-1]。时间复杂度在O（N^2）2. 二分法，首先构建一个数组res用来存储最长上升子序列，遍历整个nums，如果nums[i]在res中是最大的，则加到最后，如果不是，则替换掉比他大但是最接近他的数。这个思想就是不断的扩大其他数能进来的余地。时间复杂度，遍历nums为N，找到比他大的元素时间为logN，所以O（NlogN）

• Java

class Solution {
   
    public int lengthOfLIS(int[] nums) {
   
        if (nums.length==0 || nums==null) return 0;
        int res = 1;
        int[] dp = new int[nums.length];
        for (int i=0;i<nums.length;i++) dp[i] = 1;
        for (int i=1;i<nums.length;i++) {
   
            for (int j=0;j<i;j++) {
   
                if (nums[i]>nums[j])
                    dp[i] = Math.max(dp[i], dp[j]+1);
            }
            res = dp[i]>res?dp[i]:res;
        }
        return res;
    }
}

• Python

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

• Java

class Solution {
   
    public int lengthOfLIS(int[] nums) {
   
        int[] tails = new int[nums.length];
        int size = 0;
        for (int x : nums) {
   
            int i = 0, j = size;
            while (i != j) {
   
                int m = (i + j) / 2;
                if (tails[m] < x)
                    i = m + 1;
                else
                    j = m;
            }
            tails[i] = x;
            if (i == size) ++size;
        }
        return size;
}
}

• Python

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