最长上升子序列

2次最长上升子序列即可

#include<bits/stdc++.h>
using namespace std;
int main()
{
    const int N=10005;
    int dp1[N]={0},dp2[N]={0},height[N]={0};
    int n,mn=0x3f3f3f3f;
    while(cin>>n)
    {
        mn=0x3f3f3f3f;
        for(int i=1;i<=n;i++)
        {
            cin>>height[i];
        }
        for(int i=1;i<=n;i++)//从左往右一次最长上升子序列统计
        {
            dp1[i]=1;
            for(int j=1;j<i;j++)
            {
                if(height[i]>height[j])
                {
                    dp1[i]=max(dp1[i],dp1[j]+1);
                }
            }
        }
        for(int i=n;i>=1;i--)//从右往左一次最长上升子序列统计
        {
            dp2[i]=1;
            for(int j=n;j>i;j--)
            {
                if(height[i]>height[j])
                {
                    dp2[i]=max(dp2[i],dp2[j]+1);
                }
            }
        }
        for(int i=1;i<=n;i++)
        {
            mn=min(n-dp1[i]-dp2[i]+1,mn);
        }
        cout<<mn<<endl;
    }
}