题解 | #最长递增子序列#

本题采用类似耐心排序的算法，通过二分查找的方式，将题目的复杂度将为（NlogN)。通过二分查找的方式可以成功地获得最长递增子序列的大小，并保证所得子序列是严格字典序的。该题的难点在于如何获得子序列中的每个元素，我们采用一个index数组记录以序号为i为结尾的最长递增子序列的长度，一个MaxInd数字记录整个数列的最长递增子序列末尾元素在veci数组中的序号，并通过倒序便利将字典序最小的最长递增子序列加入到数组res中。

#include <vector>
#include <cstdio>
using namespace std;

int main() {                           //耐心排序算法
    int vecSize;
    scanf("%d", &vecSize);
    vector<int> veci = vector<int>(vecSize);
    for(int i = 0; i < vecSize; ++i)
    {
        int vec;
        scanf("%d", &vec);
        veci[i] = vec;
    }
    vector<int> pile = vector<int>(vecSize);
    vector<int> index = vector<int>(vecSize);
    int piles = 0;
    int MaxInd = 0;
    for(int i = 0; i < vecSize; ++i)
    {
        int left = 0;
        int right = piles;
        int poker = veci[i];
        while(left < right)       //只能使用左开右闭区间否则出现错误
        {
            int mid = left + (right - left) / 2;
            if(pile[mid] > poker)
            right = mid;
            else if(pile[mid] < poker)
            left = mid + 1;
            else
            right = mid;
        }
        if(left == piles) ++piles;    
        pile[left] = poker;
        index[i] = left + 1;     //记录以i结尾时最长递增子序列的长度
        if(index[i] == piles)    //MaxInd记录最长递增子序列末尾元素的序号
        {
            MaxInd = i;
        }
    }
    vector<int> res = vector<int>(piles);
    int count = piles;
    for(int i = MaxInd; i >= 0; --i)
    {
        if(index[i] == count)
        {
            res[--count] = veci[i];
        }
    }
    for(int i = 0; i < piles; ++i)
    {
        printf("%d", res[i]);
        printf(" ");
    }
    return 0;
}