贪心法解最长上升子序列

题意

给定一个长度为(N)的数列，求数值严格单调递增的子序列的长度最长是多少。

数据范围

(1 leq N leq 100000)

思路

维护一个数组 nums，要求这个数组里的元素在数值上是严格递增的。

遍历每一个数，如果这个数比数组里的最后一个数更大，那么就将这个数插入数组的最后；反之，替换掉数组中第一个大于等于这个数的元素。

最后的答案就是数组中元素的个数。

对于这个贪心策略，考虑一种理解方式：这个数组不用于记录最终的最长子序列，而是以 nums[i] 结尾的子序列长度最长为 i，即长度为 i 的递增序列中，末尾元素最小的是 nums[i]。

理解了上面这一点，正确性就显然了。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 100010;

int n;
vector<int> nums;

int main()
{
    scanf("%d", &n);
    int x;
    scanf("%d", &x);
    nums.push_back(x);
    for(int i = 2; i <= n; i ++) {
        scanf("%d", &x);
        if(x > nums[nums.size() - 1]) nums.push_back(x);
        else nums[lower_bound(nums.begin(), nums.end(), x) - nums.begin()] = x;
    }
    // lower_bound: 大于等于 x 的第一个数
    // upper_bound: 大于 x 的第一个数
    printf("%d
", nums.size());
    return 0;
}