Leetcode:300.最长上升子序列

题目描述

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

示例:

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

说明:

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

思路

思路1 动态规划

维持每个数字对应的上升子序列长度，然后根据状态转移方程$dp[i] = max(dp[j] + 1)　j\in(nums[j] < nums[i] && j < i>>)$

思路2 贪心+二分搜索

使用一个数组保存从小到大的数字，在相同的上升子序列长度只保留一个值(最小值)，然后每个数字进来二分查找找到合适的位置。

代码

代码1

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

代码2

class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0){
            return 0;
        }
        int n = nums.length;
        int[] dps = new int[n + 1];
        int len = 1;
        dps[1] = nums[0];
        for(int i = 1; i < n; i++){
            if (nums[i] > dps[len]){
                dps[++len] = nums[i];
                continue;
            }
            int left  = 1, right = len;
            int origin = 0;
            while(left <= right){
                int mid = (left + right) / 2;
                if (dps[mid] < nums[i]){
                    origin = mid;
                    left = mid + 1;
                }else{
                    right = mid - 1;
                }
            }
            dps[origin + 1] = nums[i];
        }
        return len;
    } 
}