C++, 贪心 + 二分查找

设置一个记录上升子序列状态的二维dp[n + 1][ ];

vector<vector> dp_str(n + 1, vector ());
第一维下标代表当前长度，其第二维代表最长子序列

贪心思想：若想让子序列长度更长，则应确保每次增加新元素的幅度尽可能的小，“小步多走”；

从头遍历数组，寻找 ==以当前元素为最后元素== 的上升子序列；

1. 若 当前元素 > 当前最长子序列的最后一个元素，则添加并更新最长子序列;
2. 若 当前元素 <= 当前最长子序列的最后一个元素, 则其可以替代当前最长子序列中间的某一个元素，为后面的上升序列做铺垫

   • 二分查找 在当前最长子序列中 查找 【第一个小于当前元素的元素位置pos】，并在其后替换更新
   • 按字典顺序大小 比较 【新取得的子序列temp 】 与 【已有的同长度的子序列dp_str[pos + 1]】 哪个更小，保留字典序列小的；

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
        int n = arr.size();
        // 第一维下标代表当前长度，其第二维代表最长子序列
        vector<vector<int>> dp_str(n + 1, vector<int> ());
        // 初始化第一个长度为1的开始子序列
        int len = 1; 
        dp_str[len].emplace_back(arr[0]);

        for (int i = 1; i < n; ++i) {
            // 若 当前元素 > 当前最长子序列的最后一个元素，则添加并更新最长子序列
            if (arr[i] > dp_str[len].back()) {
                ++len;
                dp_str[len] = dp_str[len - 1];
                dp_str[len].emplace_back(arr[i]);
            }
            // 若 当前元素 < 当前最长子序列的最后一个元素, 则其可以替代最长子序列中间的某一个元素
            else {
                // 二分查找 在当前最长子序列中 查找 第一个小于当前元素的元素位置，并更新
                int l = 1, r = len, pos = 0;
                while (l <= r) {
                    int mid = l + ((r - l) >> 1);
                    if (dp_str[mid].back() < arr[i]) {
                        l = mid + 1;
                        pos = mid;
                    }
                    else {
                        r = mid - 1;
                    }
                }
                // temp 为 若成功替换后，新的以arr[i]结尾，长度为pos + 1 的子序列
                vector<int> temp = dp_str[pos];
                temp.emplace_back(arr[i]);
                // 与以及存在的 同长度的 子序列 按字典大小比较，若新的更小，则更新
                if (temp < dp_str[pos + 1]) {
                    dp_str[pos + 1] = temp;
                } 
//                 // 否则， 只更新最后一个元素
//                 else {
//                     dp_str[pos + 1].back() = arr[i];
//                 }
            }
        }
        return dp_str[len];
    }
};