题意整理

• 给定一个数组arr，求arr数组的最长上升子序列。
• 可能存在多个最长上升子序列，取字典序最小的那一个。

方法一（动态规划）

1.解题思路

• 状态定义：$dp[i]dp[i]$表示以i位置元素结尾的最长上升子序列长度。
• 状态初始化：以每个位置结尾的上升子序列长度至少为1。
• 状态转移：遍历arr数组，假设当前位置为i，比较当前位置i之前的每一个元素与当前位置元素的大小，如果小于当前位置元素$arr[i]arr[i]$，说明可以接在$arr[i]arr[i]$前面。即$dp[i]=Math\mathrm{.}max(dp[i],dp[j]+1)dp[i]=Math.max(dp[i],dp[j]+1)$。

确定dp数组每一个位置的值之后，通过逆序遍历arr数组的方式，找到每一个长度对应的那个元素，赋值给结果序列即可。

这种方法运行会超时。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * retrun the longest increasing subsequence
     * @param arr int整型一维数组 the array
     * @return int整型一维数组
     */
    public int[] LIS (int[] arr) {
        int n=arr.length;
        //dp[i]表示以i位置元素结尾的最长上升子序列长度
        int[] dp=new int[n+1];
        //初始化为1
        Arrays.fill(dp,1);
        //记录最长子序列的长度
        int len=0;
        for(int i=0;i<n;i++){
            for(int j=0;j<i;j++){
                //如果小于arr[i]，则可以接在arr[i]前面
                if(arr[j]<arr[i]){
                    dp[i]=Math.max(dp[i],dp[j]+1);
                }
            }
            //计算最长子序列的长度
            len=Math.max(len,dp[i]);
        }
        
        int[] res=new int[len];
        //从后往前确定目标子序列的每一个值
        for(int i=n-1;i>=0;i--){
            if(dp[i]==len){
                res[--len]=arr[i];
            }
        }
        return res;
    }
}

3.复杂度分析

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

方法二（动态规划+二分优化）

1.解题思路

与方法一相同的是，也需要建立一个dp数组找到每一个位置对应的最长上升子序列长度，最后再通过逆序遍历arr数组的方式，找到每一个长度对应的那个元素，赋值给结果序列。不过确定dp数组的方式有所不同。

为了找到最长的上升子序列，我们可以维护一个单调递增的数组tail记录当前的最长上升子序列，如果后面出现的数$arr[i]arr[i]$比tail数组末尾元素大，则可以直接加在后面；如果不是，则找到tail数组中第一个大于等于$arr[i]arr[i]$的元素位置，并将该位置的元素替换为$arr[i]arr[i]$，因为在长度相同的情况下，当前值越小，则后面出现更长子序列的概率越大。

图解展示：

2.代码实现

import java.util.*;


public class Solution {
    /**
     * retrun the longest increasing subsequence
     * @param arr int整型一维数组 the array
     * @return int整型一维数组
     */
    public int[] LIS (int[] arr) {
        int n=arr.length;
        //维护一个单调递增tail数组
        int[] tail=new int[n];
        //dp[i]表示以i位置结尾的最长上升子序列长度
        int[] dp=new int[n];
        //最长上升子序列长度
        int len=0;
        for(int i=0;i<n;i++){
            //如果tail数组为空，或者tail数组最后一个元素小于arr[i]
            if(i==0||tail[len-1]<arr[i]){
                //直接加在最后面
                tail[len++]=arr[i];
                //记录当前长度
                dp[i]=len;
            }
            else{
                //二分法找到tail数组中第一个大于等于arr[i]的元素位置
                int index=search(tail,len,arr[i]);
                //跟新index处的值
                tail[index]=arr[i];
                //记录当前长度
                dp[i]=index+1;
            }
        }
        int[] res=new int[len];
        //从后向前依次给子序列赋值
        for(int i=n-1;i>=0;i--){
            if(dp[i]==len){
                res[--len]=arr[i];
            }
        }
        return res;
    }
    
    //二分法找tail数组中第一个大于等于arr[i]的元素位置
    private int search(int[] nums,int len,int k){
        int low=0,high=len-1;
        while(low<high){
            int mid=(high+low)/2;
            //如果大于等于k，排除mid往右的所有元素
            if(nums[mid]>=k){
                high=mid;
            }
            //否则排除mid以及mid往左的所有元素
            else{
                low=mid+1;
            }
        }
        return low;
    }
}

3.复杂度分析

• 时间复杂度：需要遍历$arrarr$数组每一个元素，对于每一个元素需要确定其在$tailtail$数组中的位置，每次确定位置需要$lo{g}_{2}nlog\_2n$的时间复杂度，所以时间复杂度为$O(nlo{g}_{2}n)O(nlog\_2n)$。
• 空间复杂度：需要额外大小为n的dp数组和tail数组，所以空间复杂度是$O(n)O(n)$。