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

最长上升子序列(一)

题目描述

给定一个长度为 n 的数组 arr，求它的最长严格上升子序列的长度。

所谓子序列，指一个数组删掉一些数（也可以不删）之后，形成的新数组。例如 [1,5,3,7,3] 数组，其子序列有：[1,3,3]、[7] 等。但 [1,6]、[1,3,5] 则不是它的子序列。

方法一：动态规划方法

解题思路

对于本题目的求解，利用动态规划，dp[i]表示以下标i结尾的最长上升子序列的长度。首先初始化，dp[i]=1，因为以任意下标结尾的子序列长度大于等于1。然后遍历数组中所有的数，再遍历当前数之前的所有数，只要前面某个数小于当前数，则要么长度在之前基础上加1，要么保持不变。因此有状态转移方程：

$dp[i]=max(dp[i],dp[j]+1)dp[i]\; =\; max(dp[i],\; dp[j]+1)$

解题代码

import java.util.*;

public class Solution {
    public int LIS (int[] arr) {
        int n=arr.length;
        //特殊请款判断
        if(n==0) return 0;
        //dp[i]表示以下标i结尾的最长上升子序列长度
        int[] dp=new int[n];
        for(int i=0;i<n;i++)
        {
            dp[i]=1;
            for(int j=0;j<i;j++)
            {
                if(arr[i]>arr[j])
                {
                    //只要前面某个数小于当前数，则要么长度在之前基础上加1，要么保持不变，取较大者
                    dp[i]=Math.max(dp[i],dp[j]+1);
                }
            }
        }
        //返回所有可能中的最大值
        return Arrays.stream(dp).max().getAsInt();
    }
}

复杂度分析

时间复杂度：两层循环，因此时间复杂度为$O(N^2)O(N^2)$。

空间复杂度：使用dp数组，因此空间复杂度为$O(N)O(N)$，其中N为dp数组的大小。

方法二：优化的方法

解题思路

我们可以对上面的方法进行优化，申请一个单调递增的数组，遍历arr数组中所有的数，如果申请的数组为空或者末尾值小于arr[i]，那么直接加在其后面。否则，二分法找到当前数在申请数组中的位置，替换掉原来的位置。同时，申请一个end变量让其记录数组的最后一个元素的位置，那么end+1便是最终上升子序列的长度。

解题代码

import java.util.*;

public class Solution {
    public int LIS (int[] arr) {
        int n=arr.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]<arr[i])
            {
                tail[++end]=arr[i];
            }
            //否则找到tail数组中第一个大于等于arr[i]的数的下标，替换为arr[i]
            else
            {
                int index=binarySearch(tail,end,arr[i]);
                tail[index]=arr[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;
    }
}

复杂度分析

时间复杂度：遍历数组加上使用二分法，因此时间复杂度为$O(N\ast logN)O(N*logN)$。

空间复杂度：申请了一个大小为n的数组，因此空间复杂度为$O(N)O(N)$。