题意整理

对于给定的输入序列，要从其中找到一个子序列，满足序列中的数字是单调上升的，在满足的子序列中找到长度最长的并进行输出。子序列是指一个数组删除若干元素，但不改变其他元素相对位置形成的序列。在有多个子序列满足的条件下，输出字典序最小的子序列。
例如：
输入：[1,2,8,6,4]
返回值：[1,2,4]
其最长递增子序列有3个，（1，2，8）、（1，2，6）、（1，2，4）其中第三个 按数值进行比较的字典序 最小，故答案为（1，2，4）

思路

  • 先获得最长递增子序列的长度
  • 根据长度逆序遍历输入序列，获得最长递增子序列

第一个想到的是暴力动态规划，但写出代码过后提交超时，一度不知道怎么优化，看了各路大佬的题解后才知道用二分进行优化，最终也成功自己实现了优化的动态规划代码。

解法一 暴力动态规划

首先定义dp数组：动态规划的dp数组存放以arr[i]结尾的递增子序列的个数。
获得dp数组后，逆序遍历一遍arr数组即可获得最长递增子序列。
base case: 初始时dp数组每个元素初始化为1，显然对每一个arr元素而言，它自身即为一个递增子序列。
递推关系： 对每一个，需要和前面所有元素进行比较，若且 （即 是以结尾的最长递增子序列的成员）则
由递推关系很容易得知对于dp数组中值相同的元素，对应到arr数组中一定是在dp数组中相同值最后的元素最小对，容易看出, 显然，因此要获得字典序最小的最长递增子序列，只需逆序遍历一遍arr数组，选择第一个满足条件的元素进入结果序列即可。
运行提交会超时。

示例

给定输入: [2,1,5,3,6]
示例如下图：
图片说明

代码

class Solution {
public:
    /**
     * retrun the longest increasing subsequence
     * @param arr int整型vector the array
     * @return int整型vector
     */

    vector<int> LIS(vector<int>& arr) {
        // write code here
        //第一步，先获得存放arr[i]结尾的递增子序列的个数的数组dp
        int length = arr.size();
        vector<int> dp(length, 1); //dp数组存放arr[i]结尾的递增子序列的个数
        int maxLen = 1; //记录最长子序列的长度
        if (length == 1)
            return dp;
        for (int i = 0; i < length; i++){//计算dp[i]
            for (int j = 0; j < i; j++){// dp[i]初始为1，计算dp[i]时arr[i]与前面所有arr[j]进行比较，取最大
                if (arr[j] < arr[i]) //若arr[j] < arr[i], 则arr[j]属于以arr[i]结尾的子序列
                    dp[i] = dp[j]+1 > dp[i] ? dp[j]+1 : dp[i]; 
            }
            maxLen = maxLen>dp[i] ? maxLen : dp[i];
        }
        //第二步，获得字典序最小的最长子序列，由dp的计算过程可知，若dp[i] == dp[j](i > j), 则arr[i] < arr[j]
        vector<int> res(maxLen); //最长子序列
        for (int i = length; i >= 0; i--){
            if (dp[i] == maxLen){ //从后往前遍历dp数组,第一个等于maxLen的下标进入最终子序列
                res[--maxLen] = arr[i];
            }
        }
        return res;
    }
};

复杂度分析

时间复杂度：构建dp数组用了两层循环为,获得结果序列最大为，总的时间复杂度为
空间复杂度：需要构建dp数组，空间复杂度为

解法二 动态规划+二分优化

维护一个tails数组，存放长度为i+1的递增子序列的最小的末尾元素。容易证明，tails一定是单调递增的序列，例如, 一定是给定序列中最小的元素即对应的长度为2的递增子序列，有, 显然， 同理, 可知arr数组的最长递增子序列长度为3，值为。由于tails数组单调递增，因此遍历arr数组时对可以采用二分查找，找到满足的位置，并将插入该位置。由此所得tails数组的长度即为arr数组的最长递增子序列的长度。
由于要返回最长递增子序列，还需要维护一个相当于暴力动态规划中的辅助数组记录的对应的最长递增子序列的长度。构建tails数组时，若插入到tails末尾，即tails长度增加，则, 若插入tails中间位置，则为tails被插入位置的下标+1（tails数组的下标表示子序列长度-1），最后逆序遍历即可获得答案。
运行提交顺利通过。

示例

给定输入: [2,1,5,3,6]
示例如下图：
图片说明

代码

class Solution {
public:
    /**
     * retrun the longest increasing subsequence
     * @param arr int整型vector the array
     * @return int整型vector
     */

    vector<int> LIS(vector<int>& arr) {
        // write code here
        //第一步，先获得tials数组,tails[i]存放长度为i+1的递增子序列的最小的末尾元素
        int length = arr.size();
        vector<int> tails(length, 0), dp(length,0); 
        if (length <= 1)
            return arr;
        int size = 0; //tails当前长度
        for (int i = 0; i < length; i++){//遍历一遍arr

            int low = 0, high = size;
            while (low != high){ //二分查找arr[i]应该替换或插入的位置
                int mid = (low + high) / 2;
                if (arr[i] > tails[mid])
                    low = mid + 1;
                else
                    high = mid;
            }
            tails[low] = arr[i]; //更新arr[i]到应该插入或替换的位置
            if (low == size) {//若arr[i]插入到最后的位置，tails长度大小size++
                size++;
                dp[i] = size; //记录当前下标对应最长递增子序列长度,该长度为当前size
            }
            else
                dp[i] = low + 1; //记录当前下标对应最长递增子序列长度,该长度为被替换的元素所对应的长度
        }
        //第二步，获得字典序最小的最长子序列，由size得最长递增子序列的长度，且tails[size-1]存储了
        //该子序列的末尾元素，因此只需倒序遍历找出以tials[size-1]结尾的递增子序列即可
        vector<int> res(size); //最长子序列
        for (int i = length - 1; i >= 0; i--){
            if (dp[i] == size) //找到tail
                res[--size] = arr[i];
        }
        return res;

    }
};

复杂度分析

时间复杂度：构建tails数组，外层循环为,内层二分法为，遍历dp数组最大为,总的时间复杂度为
空间复杂度：需要两个辅助数组tails和dp，空间复杂度为