最长递增子序列

1、题目描述

给定数组arr，设长度为n，输出arr的最长递增子序列。（如果有多个答案，请输出其中字典序最小的）

2、解题思路

代码可以分成两个部分：
part1:确定最长子序列，并记录位置。

part2：通过位置倒序，确定字典序最小的那组。
注意：(1)在子序列中替换不影响子序列的排序且子序列最小的数
（2）记录数字在子序列数组中的位置

3、代码

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
        vector<int> result;//存储结果
        vector<int> pos; // 存储在结果数组中的位置
        int len = arr.size();
        result.push_back(arr[0]);
        pos.push_back(0);
        //贪心获取最长子序列
        for(int i = 1;i<len;i++){
            if(arr[i]>result.back()){
                result.push_back(arr[i]);
                pos.push_back(result.size()-1);
            }else{
                //在合适的位置(result是有序的，可以使用二分查找)
                int j = 0;
                for(j = result.size()-1;j>=0;j--){
                    if(result[j]<arr[i]){
                        break;
                    }
                }
                //替换
                result[j+1] = arr[i];
                pos.push_back(j+1);
            }
        }
        //从后往前处理最长子序列
        int tmpLen = result.size()-1;
        for(int i = len-1;i>=0;i--){
            if(pos[i]==tmpLen){
                result[tmpLen] = arr[i];
                tmpLen--;
            }
        }
        return result;
    }
};