da(答) an(案)
2024-01-20 00:54:47
发布于:广东
5阅读
0回复
0点赞
#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int w[N], f1[N], f2[N];
int n;
//最长上升子序列模板,(int* f)是引用arr
void lis(int* f)
{
for (int i = 1; i<=n; i++) {
f[i] = 1;
for (int j = 1; j<i; j++) {
if (w[j] < w[i]) f[i] = max(f[i], f[j]+1);
}
}
}
int main ()
{
//接收数据
cin >> n;
for (int i = 1; i<=n; i++) cin >> w[i];
//求两遍,一次最长上升子序列,一次最长下降子序列
lis(f1);
reverse(w+1, w+n+1);
lis(f2);
//把每个峰值点的上升和下降加在一起,算所有点作为峰值的max即可
int x = 0;
for (int i = 1; i<=n; i++) x = max(x, f1[i]+f2[n-i+1]); //这里因为下降子序列是反着求的,所以下标也是需要反着来
cout << x-1 << endl;
return 0;
}
这里空空如也
有帮助,赞一个