最长上升子序列(二)

题目描述

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

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

方法一:动态规划方法

解题思路

对于本题目的求解,利用动态规划,dp[i]表示以下标i结尾的最长上升子序列的长度。首先初始化,dp[i]=1,因为以任意下标结尾的子序列长度大于等于1。然后遍历数组中所有的数,再遍历当前数之前的所有数,只要前面某个数小于当前数,则要么长度在之前基础上加1,要么保持不变。有状态转移方程如下,并且此时的j代表在i位置前面的任何一个元素,用一个循环来表示,并且需要满足条件为arr[i] > arr[j]。

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

alt

解题代码

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(N2)O(N^2)

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

方法二:优化的方法

解题思路

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

alt

解题代码

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(NlogN)O(N*logN)

空间复杂度:申请了一个大小为n的数组,因此空间复杂度为O(N)O(N)