TB椰程 TypeBuddy 打字搭子

最长上升子序列

CSP-J · 编程模板 · 片段 · cpp · 难度 4/5 · 共 551 字

n log n：维护上升尾数组二分插入

  • 动态规划
  • 最长上升子序列

前置内容

正文

// LIS：最长上升子序列
// O(n^2)：以 i 结尾的长度
// O(n log n)：维护上升尾数组
// 这里给 n log n 写法
#include <cstdio>
#include <algorithm>
using namespace std;
int a[100005], t[100005], n, len = 0;
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    // 二分找第一个 >= a[i]
    for (int i = 1; i <= n; i++) {
        int p = lower_bound(
            t + 1, t + len + 1, a[i]) - t;
        // 无则接在末尾，延长 LIS
        if (p > len) t[++len] = a[i];
        else t[p] = a[i];
    }
    // len 即 LIS 长度
    printf("%d", len);
    return 0;
}

CSP-J · 编程模板的其它内容

打字首页 · 词库画廊 · 编程打字 · 指法入门 · 天梯榜 · 数据分析 · 班级课堂 · 关于我们
椰程 TypeBuddy 打字搭子 —— 键盘指法练习 · 单词记忆 · 班级课堂 · 在线 PK