1802: 【提高】最长上升子序列LIS（2）

内存限制：128 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：5 解决：2

题目描述

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

输入

第一行包含整数N。
第二行包含N个整数，表示完整序列。
1≤N≤100000，−109≤数列中的数≤109

输出

输出一个整数，表示最大长度。

样例输入 复制 

6
1 3 2 8 5 6

样例输出 复制 

4

提示

#include<bits/stdc++.h>

using namespace std;
//dp:长度为i的LIS的最后一位最小值是多少
int a[100100], dp[100100];
int i, n, l, r, mid;
int main() {
    scanf("%d", & n);
    for (i = 1; i <= n; i++) {
        scanf("%d", & a[i]);
    }
    //边界
    dp[1] = a[1];
    int len = 1; //LIS 的长度
    //从第2个数开始求解
    for (i = 2; i <= n; i++) {
        //如果 a[1]比 dp最后一位大,a[1]直接续上去,增加 LIS 的长度
        if (a[i] > dp[len]) {
            len++;
            dp[len] = a[i];
        } else {
            //二分查找到dp数组中第1个>=a[1]的元素下标，普换(dp数组一定是递增的)
            l = 1;
            r = len;
            while (l <= r) {
                mid = (l + r) / 2;
                if (a[i] <= dp[mid]) r = mid - 1;
                else l = mid + 1;
            }
            //普换
            dp[l] = a[i];
        }
    }
    printf("%d", len);
    return 0;
}

来源/分类

提交提交记录统计露一手!