题目描述
给一个数组,求满足^形状的最长长度。
f1-预处理数组+枚举峰值点 |
基本分析
- 每一个点都可能是峰值点,需要每次都计算2次最长上升子序列吗?不需要,全部计算完再枚举
- 怎么转化i到n-1的最长下降子序列?从n-1到i的最长上升子序列
代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
int a[N], f[N], g[N];
int n;
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++)
scanf("%d", &a[i]);
for (int i = 0; i < n; i ++)
{
f[i] = 1;
for (int j = 0; j < i; j ++)
{
if (a[i] > a[j])
f[i] = max(f[i], f[j] + 1);
}
}
for (int i = n-1; i >=0; i--)
{
g[i] = 1;
for (int j = n-1; j > i; j--)
{
if (a[i] > a[j])
g[i] = max(g[i], g[j] + 1);
}
}
int ans = 0;
for (int i = 0; i < n; i ++)
ans = max(ans, f[i] + g[i] - 1);
printf("%d\n", ans);
return 0;
}
总结
- 提前与处理出两个子序列长度,然后枚举峰值统计。