题解 | #最长上升子序列(二)#

题意整理

• 给定一个长度为n的数组。
• 求它的最长上升子序列的长度。子序列是指按原来数组顺序取的若干个数字组成的序列，上升子序列是指序列中元素严格单调递增。

方法一（动态规划）

1.解题思路

• 状态定义：$dp[i]dp[i]$表示以下标i结尾的最长上升子序列的长度。
• 状态初始化：以任意下标结尾的上升子序列长度不小于1，故初始化为1。
• 状态转移：遍历数组中所有的数，再遍历当前数之前的所有数，只要前面某个数小于当前数，则要么长度在之前基础上加1，要么保持不变，取两者中的较大者。即$dp[i]=Math\mathrm{.}max(dp[i],dp[j]+1)dp[i]=Math.max(dp[i],dp[j]+1)$。

数据量较大时，这种方法运行会超时。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 给定数组的最长严格上升子序列的长度。
     * @param arr int整型一维数组 给定的数组
     * @return int整型
     */
    public int LIS (int[] a) {
        int n=a.length;
        //特殊请款判断
        if(n==0) return 0;
        //dp[i]表示以下标i结尾的最长上升子序列长度
        int[] dp=new int[n];
        for(int i=0;i<n;i++){
            //初始化为1
            dp[i]=1;
            for(int j=0;j<i;j++){
                if(a[i]>a[j]){
                    //只要前面某个数小于当前数，则要么长度在之前基础上加1，要么保持不变，取较大者
                    dp[i]=Math.max(dp[i],dp[j]+1);
                }
            }
        }
        int res=1;
        //找到所有可能中的最大值
        for(int i=0;i<n;i++){
            res=Math.max(res,dp[i]);
        }
        return res;
    }
}

3.复杂度分析

• 时间复杂度：两层循环，最多执行$n\ast (n-1)\mathrm{/}2n*(n-1)/2$次，所以时间复杂度是$O(n^2)O(n^2)$。
• 空间复杂度：需要额外大小为n的dp数组，所以空间复杂度为$O(n)O(n)$。

方法二（二分优化）

1.解题思路

• 维护一个单调递增的tail数组。
• 遍历arr数组中所有的数，如果tail数组为空或tail数组末尾值小于$arr[i]arr[i]$，直接加在后面。否则，二分法找到当前数在tail数组中的位置，替换掉原来位置的数。
• end总是指向tail数组最后一个元素的位置，所以end+1即为最终tail数组的长度，也就是最长上升子序列的长度。

图解展示：

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 给定数组的最长严格上升子序列的长度。
     * @param arr int整型一维数组 给定的数组
     * @return int整型
     */
    public int LIS (int[] a) {
        int n=a.length;
        //特殊请款判断
        if(n==0) return 0;
        //维护一个单调递增的数组
        int[] tail=new int[n];
        //指向tail数组的最后一位
        int end=-1;
        for(int i=0;i<n;i++){
            //如果数组为空或数组末尾值小于arr[i]，直接加在后面
            if(i==0||tail[end]<a[i]){
                tail[++end]=a[i];
            }
            //否则找到tail数组中第一个大于等于arr[i]的数的下标，替换为arr[i]
            else{
                int index=binarySearch(tail,end,a[i]);
                tail[index]=a[i];
            }
        }
        return end+1;
    }

    //二分法找到tail数组中第一个大于等于arr[i]的数的下标
    private int binarySearch(int[] tail,int end,int target){
        int l=0;
        int r=end;
        while(l<r){
            int mid=l+(r-l)/2;
            if(tail[mid]>=target){
                r=mid;
            }
            else{
                l=mid+1;
            }
        }
        return l;
    }
}

3.复杂度分析

• 时间复杂度：需要遍历数组中所有的数，对于特定的数（小于等于有序数组中的最大值），需要通过二分法找到其在有序数组中的位置，最坏情况下所有的数都需要二分查找确定位置，所以时间复杂度是$O(n\ast lo{g}_{2}n)O(n*log\_2n)$。
• 空间复杂度：需要额外维护一个大小为n的有序数组，所以空间复杂度为$O(n)O(n)$。