想着从前往后做一遍最长上升,再求一遍最长下降。 为什么错啊 !
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int h[N];
int up[N], down[N];//求最长上升子序列和最长下降子序列
int n;
int main()
{
cin >> n;
for(int i = 1; i <= n; i ++) cin >> h[i];
//求最长上升子序列
for(int i = 1; i <= n; i ++)
{
up[i] = 1;
for(int j = 1; j < i; j ++)
{
if(h[j] < h[i]) up[i] = max(up[i], up[j] + 1);
//if(h[j] > h[i]) down[i] = max(down[i], down[j] + 1);
}
}
//求最长下降子序列
for(int i = 1; i <= n; i ++)
{
down[i] = 1;
for(int j = 1; j < i; j ++)
{
// if(h[j] < h[i]) up[i] = max(up[i], up[j] + 1);
if(h[j] > h[i]) down[i] = max(down[i], down[j] + 1);
}
}
int res = 0;
for(int i = 1; i <= n; i ++) res = max(res, up[i] + down[i] - 1);
cout << n - res << endl;
return 0;
}