最长上升子序列

5月5日 · 2018年

最长上升子序列

用一个数组保存当前的最长上升子序列

显然初始情况就是原序列的第一个元素

之后,遍历序列,如果当前的元素比数组最后一个元素大

那么显然把它加入到这个数组中可以得到更长的上升子序列

如果不是,即当前的元素小于等于数组最后一个元素

由于存在一种可能是从这个更小的元素开始,往后,可以得到更长的上升子序列

所以要把这个元素也留下来,同时,把在这个元素之前出现的比它小的元素加到它的前面组成另一个新的序列

那么可以得到若干个这样的序列

取最长的即可

另外,由于只需要求出最长的长度,所以没有必要留下每一个新的序列

这些可能的序列可以直接在刚才那个数组前面修改

显然,修改数组最后一个元素之前的元素的值不会改变数组的长度

而且,事实上,由于数组的元素是严格单调递增的,所以可以用二分法快速的找到比当前元素小的元素

那么,状态转移的方程表示如下
$$
如果current>array[length],将current加入到array后面,使序列长度加1 \\
否则,将array中第一个不小于current的值修改为current
$$
代码如下:

#include <bits/stdc++.h>

#define MAXN 1000007

using namespace std;

int main() {
    int n;
    scanf("%d", &n);
    int a[MAXN] = {0};
    int dp[MAXN] = {0};
    for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
    int ans = 0;
    dp[ans] = a[0];
    for (int i = 1; i < n; ++i)
        if (a[i] > dp[ans])
            dp[++ans] = a[i];
        else
            *lower_bound(dp, dp + ans, a[i]) = a[i];
    printf("%d\n", ans + 1);
    return 0;
}
0 条回应
验证码
输入运算符及数字使等式成立
{{comment.validate_num1}} = {{comment.validate_num2}}
点赞确定
退出登录?
取消 确定