(动态规划)LC 最长递增子序列

问题

方法一：动态规划

用一个数组dp[i]来表示以nums[i]结尾的最长子序列的长度(必须包含nums[i])，则有以下转移式：
d p [ i ] = m a x { d p [ j ] ∣ 0 < = j < i 且 n u m s [ i ] > n u m s [ j ] } + 1 dp[i] = max\{dp[j] | 0 <= j < i 且nums[i]>nums[j]\} + 1 dp[i]=max{dp[j]∣0<=j<i且nums[i]>nums[j]}+1
如果对所有的nums[j]都大于nums[i]，则dp[i]=1

public int lengthOfLIS(int[] nums) {
        int len = nums.length;
        int[] length = new int[len];
        Arrays.fill(length,1);
        for(int i = 0; i < len; i++){
            for(int j = i + 1; j < len; j++){
                if(nums[j] > nums[i]){
                    length[j] = Math.max(length[j] , length[i] + 1);
                }
            }
        }
        int max = -1;
        for(int l : length)
            max = Math.max(l,max);
        return max;
    }

• 时间复杂度：O(n²)
• 空间复杂度：O(n)

方法二：动态规划+二分查找

改变一下动态规划的状态表示形式，令dp[i]表示长度为i的子序列的最后一个元素的最小值，令length代表目前的最长子序列，当构建好dp[]时，length即最后的答案。

容易证得dp[i]是单调递增的，因为若存在一个dp[i]<dp[i-1]，则代表长度为i的最后一个元素a，比长度为i-1的最后一个元素b还有小，那么肯定可以将长度i-1的子序列的最后一个元素更新为a，a!=b，显然假设不成立

在构造dp[]时，遍历nums[]

• 如果nums[i]大于dp[length]，说明nums[i]可以放到长度为length的子序列的最后，构成一个长度为length+1的子序列，且该子序列的最后一个元素为nums[i]。所以更新dp[length+1]=nums[i],length++
• 如果nums[i]小于dp[length]，可以遍历dp[1]到dp[length-1]，找到第一个比nums[i]大的位置j,更新dp[j]=nums[i]。因为dp[j]表示在遍历到nums[i]之前，长度为j的子序列的最后一个元素为dp[j]，而nums[i]小于dp[j]，又可以作为一个长度为j的子序列的最后一个元素，所有更新dp[j]为nums[i]。又因为dp[]是单调递增的，所以可以用二分的方式来找这个j

public int lengthOfLIS(int[] nums) {
        int len = nums.length;
        int[] dp = new int[len+1];
        dp[1] = nums[0];
        int length = 1;
        for(int i = 1;i < len; i++){
            if(nums[i] > dp[length]){
                dp[++length] = nums[i];
            }else {
                int idx = search(dp, 1, length,nums[i]);
                dp[idx] = nums[i];
            }
        }
        return length;
    }
    /**
     * 选择第一个大于num的坐标
     * @param dp
     * @param start
     * @param end
     * @return
     */
    public int search(int[] dp , int start, int end , int num){
        int left = start ,right = end, mid;
        while(left < right){
            mid = left + (right - left) / 2;
            if(dp[mid] < num){
                left = mid + 1;
            }else if(dp[mid] > num){
                right = mid;
            }else {
                return mid;
            }
        }
        return left;
    }

• 时间复杂度：O(nlogn)
• 空间复杂度：O(n)