AcWing 1490. 最长上升子串 --前后缀分离法
原题链接
简单
作者:
我要出去乱说
,
2021-02-04 09:58:20
,
所有人可见
,
阅读 434
前后缀分离
#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]:以i结尾的单调上升子串的最大长度
for (int i = 1; i <= n; i ++ )
if (a[i] > a[i - 1]) f[i] = f[i - 1] + 1;
else f[i] = 1;
//预处理g[i]:以i开头的单调上升子串的最大长度
for (int i = n; i >= 1; 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, f[i - 1] + g[i + 1]); //前后能拼接在一起的情况
else res = max(res, max(f[i - 1], g[i + 1])); //前后不能拼在一起的情况
}
cout << res << endl;
return 0;
}