最长递增子序列

题目描述
给定数组arr，设长度为n，输出arr的最长递增子序列。（如果有多个答案，请输出其中字典序最小的）
示例1：
输入
[2,1,5,3,6,4,8,9,7]
输出
[1,3,4,8,9]

示例2：
输入
[1,2,8,6,4]
输出
[1,2,4]

说明：其最长递增子序列有3个，（1，2，8）、（1，2，6）、（1，2，4）其中第三个字典序最小，故答案为（1，2，4）
解题思路
第一次解题，看了评论区答案，大概意思是用了二分法+动态规划，但是不清楚二分法用在什么地方了（哭）
1：解决两个问题，第一：确定这个子序列的长度；第二是确定序列的具体元素。（难不成这里是二分法？）
2：首先设定两个数组，res[]存放子序列，maxlan[i]存放以第i个元素结尾的最长子序列的长度。将arr[0]写入res,maxlan[0] = 1;
3：遍历传进数组arr的每个元素，判断是否大于res的尾元素，若大于，则直接继续写入，maxlan的大小为res的长度。若不大于，则寻找res中第一个大于arr[i]的元素的位置，并用arr[i]替代，maxlan的大小为此时位置+1；遍历完得到子序列的长度res.size()和以每个元素结尾的最长子序列的长度maxlan。
4：再次遍历每一个元素，从后向前遍历，判断maxlan[i]中的 元素与是否是第j个元素。（其实有点难理解，要用例子说明）。如果相等的话，则将这个元素存储到res相应的位置上。

class Solution {
public:
    /**
     * retrun the longest increasing subsequence
     * @param arr int整型vector the array
     * @return int整型vector
     */
    vector<int> LIS(vector<int>& arr) {//传入的是数组，返回的也是数组

        vector<int > res;
        vector<int> maxlan;
        if(arr.size()<1) return res;
        res.emplace_back(arr[0]);//emplace_back和push_back的作用相同。
        maxlan.emplace_back(1);
        for(int i=1;i<arr.size();i++){
            if(arr[i]>res.back()){
                res.emplace_back(arr[i]);
                maxlan.emplace_back(res.size());
            }else{
                int pos = lower_bound(res.begin(), res.end(), arr[i])-res.begin();
//这个函数lower_bound(),是找到数组从开始到结尾第一个比arr[i]大的元素的位置，
//减去首元素的位置是因为有时候begin并不是首元素。（好像又把自己绕进去，要重新思考的）
                res[pos] = arr[i];
                maxlan.emplace_back(pos+1);
            }
        }
        for(int i=arr.size()-1,j=res.size();j>0;--i){
            if(maxlan[i] == j){
                res[--j] =arr[i];//--j是因为如果res长度是3，最后一个元素应该是res[2].
            }
        }
        return res;
    }
};