python/TangDou/AcWing/LIS/1014_2.cpp

#include <bits/stdc++.h>

using namespace std;
const int N = 1010;
int n, a[N];

// f[i]:长度为i的正序递增序列中，末尾元素最小的是f[i]
// p1[i]:记录第i个数字被放的f数组中位置,也就是正序排名第几
int f[N], fl, p1[N];

// g[i]:长度为i的倒序递增序列中，末尾元素最小的是g[i]
// p2[i]:记录第i个数字被放的g数组中位置,也就是倒序排名第几
int g[N], gl, p2[N];

int res;

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];

    // 正向
    f[0] = a[0];
    p1[0] = 1;

    for (int i = 0; i < n; i++)
        if (a[i] > f[fl]) {
            f[++fl] = a[i];
            p1[i] = fl;
        } else {
            int t = lower_bound(f, f + fl, a[i]) - f;
            f[t] = a[i];
            p1[i] = t;
        }

    // 反向
    g[0] = a[n - 1];
    p2[n - 1] = 1;

    for (int i = n - 1; i >= 0; i--)
        if (a[i] > g[gl]) {
            g[++gl] = a[i];
            p2[i] = gl;
        } else {
            int t = lower_bound(g, g + gl, a[i]) - g;
            g[t] = a[i];
            p2[i] = t;
        }

    for (int i = 0; i < n; i++) res = max(res, p2[i] + p1[i] + 2 - 1);

    printf("%d\n", res);
    return 0;
}