问最多修改一个数字,序列可获得地最大严格递增字段长度为多大;
维护一个L[i] 数组
L[i] 表示第一个a[i] <= a[i - 1] 的位置
L[1] = 1;
对于每个位置i
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;
const int inf = 1e9;
int a[maxn];
int L[maxn];
int main() {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
L[1] = 1;
for (int i = 2; i <= n; i++) {
L[i] = L[i - 1];
if (a[i] <= a[i - 1]) L[i] = i;
}
a[0] = -inf;
int ans = 1;
for (int i = 2; i <= n; i++) {
int j = L[i];
if (j == 1) {
ans = max(ans, i - j + 1);
} else {
if (j == i) {
ans = max(ans, i - L[j - 1] + 1);
} else {
int k = j - 1;
int w1 = a[j + 1] - 1;
if (w1 > a[k]) {
ans = max(ans, i - L[k] + 1);
}
int w2 = a[j] - 1;
if (w2 > a[k - 1]) {
ans = max(ans, i - L[k] + 1);
}
ans = max(ans, i - j + 2);
}
}
}
printf("%d\n", ans);
return 0;
} 
京公网安备 11010502036488号