二维dp(之前的奇怪做法)

#include <cstdio>
#include <iostream>
using namespace std;
const int N = 1009;
int a[N], dp[N][2], n;
//dp[][0]表示从起始到该位置单调递减的序列,dp[][1]表式从起始到该位置单调递增的序列
int main()
{
    scanf("%d",&n);
    for(int i=0; i<n; i++)
    {
        scanf("%d",&a[i]);
        dp[i][0] = dp[i][1] = 1;
    }
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<i; j++)
        {
            if(a[i]>a[j])
            {
                dp[i][1] = max(dp[j][1]+1,dp[i][1]); // 对于在dp[i][1]必须满足从起始到i-1递增
            }
            else if(a[i]<a[j])
            {
                dp[i][0] = max(max(dp[j][0]+1,dp[j][1]+1),dp[i][0]); 
                /* 对于dp[i][0]之前可以从起始到i-1递增(i为拐点),也可以满足从起始到i-1递减*/
            }
        }
    }
    int ans = -1;
    for(int i=0; i<n; i++)
    {
        ans = max(ans,max(dp[i][0],dp[i][1]));
    }
    printf("%d\n",ans);
    return 0;
}

正经的做法

// 正反跑两遍,最长上升子序列模型
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1009;
int h[N]; 
int f1[N]; //  f1[i]是以h[i]为结尾的最长上升子序列(下标顺序是从0到n)
int f2[N]; //  f2[i]是以h[i]为结尾的最长上升子序列(下标顺序是从n到0)
int n;
int ans;
int main()
{
    cin >> n;
    for(int i=0; i<n; i++) cin >> h[i];
    for(int i=0; i<n; i++) f1[i] = f2[i] = 1;
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<i; j++)
        {
            if(h[i] > h[j]) f1[i] = max(f1[i], f1[j] + 1);
        }
    }
    for(int i= n-1; i>=0; i--)
    {
        for(int j=n-1; j>i; j--)
        {
            if(h[i] > h[j]) f2[i] = max(f2[i], f2[j] + 1);
        }
    }
    for(int i=0; i<n; i++) ans = max(ans, f1[i] + f2[i] - 1); // 多算了一次 拐点h[i]
    cout << ans << endl;
    return 0;
}