zhi识点

1.预处理的目的是为了降低时间复杂度

#include <bits/stdc++.h>
#define N 1010
using namespace std;

int n;
int l[N], r[N], a[N];

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

    for(int i = 1; i <= n; ++ i) 
    {
        l[i] = 1;
        for(int j = 1; j < i; ++ j)
            if(a[i] > a[j])
                l[i] = max(l[i], l[j] + 1);
    }

    for(int i = n; i; -- i)
    {
        r[i] = 1;
        for(int j = n; j > i; -- j)
            if(a[i] > a[j])
                r[i] = max(r[i], r[j] + 1);
    }

    int res = INT_MIN;
    for(int i = 1; i <= n; ++ i) res = max(res, l[i] + r[i]);
    cout << res - 1 << endl;
}