AcWing 1490. 最长上升子串
原题链接
简单
作者:
刘杰
,
2022-02-25 20:34:39
,
所有人可见
,
阅读 205
C++ 代码
/*
##枚举删除
##递推
##a
##a[i] < a[i+1] f[i-1] + g[i+1]
##a[i-1] > a[i] max(f[i-1], g[i+1])
*/
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n;
int a[N], f[N], g[N];
int main(){
scanf("%d", &n);
for(int i = 1; i<= n; i++) scanf("%d", &a[i]);
//预处理f[i],g[i]
for(int i =1; i <=n; i++){
if(a[i] > a[i -1]) f[i] = f[i -1] + 1;
else f[i] = 1;
}
for(int i = n; i; i--){
if(a[i] < a[i+1]) g[i] = g[i+1] +1;
else g[i] = 1;
}
int res =0;
//枚举删除
for(int i = 1; i <= n; i++){
if(a[i-1] >= a[i+1]) res = max(res, max(f[i-1], g[i+1]));
else res = max(res, f[i -1]+ g[i+1]);
}
cout << res <<endl;
return 0;
}