枚举
枚举删除每个数后的最长上升字串的最大长度。
$l[i]$表示以i结尾的连续上升字串长度,$r[i]$表示以i开头的连续上升字串长度。
若删除$a[i]$后还满足$a[i - 1] < a[i + 1]$,则说明删除第i个数后,连续上升子串长度为$l[i - 1] + r[i + 1]$
若不满足,则说明删除后,前后连续子串是独立的,即$max(l[i - 1], r[i + 1])$
时间复杂度$O(N)$,空间复杂度$O(N)$,
AC代码
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int n;
int a[N];
int l[N], r[N];//l[i]表示以i结尾的连续上升字串长度,r[i]表示以i开头的连续上升字串长度
int main() {
//读入
cin >> n;
for (int i = 0 ; i < n ; i ++) cin >> a[i];
//求l
l[0] = 1;
for (int i = 1 ; i < n ; i ++) {
if (a[i] > a[i - 1])
l[i] = l[i - 1] + 1;
else l[i] = 1;
}
//求r
r[n - 1] = 1;
for (int i = n - 2 ; i >= 0 ; i --) {
if (a[i] < a[i + 1])
r[i] = r[i + 1] + 1;
else r[i] = 1;
}
//枚举删除的数
int res = 0;
for (int i = 0 ; i < n ; i ++) {
if (!i) res = max(res, r[i + 1]);
else if (i == n - 1) res = max(res, l[i - 1]);
else if ( a[i - 1] < a[i + 1]) res = max(res, l[i - 1] + r[i + 1]);
else res = max(res, max(l[i - 1], r[i + 1]));
}
cout << res;
return 0;
}