问最多修改一个数字,序列可获得地最大严格递增字段长度为多大;
维护一个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; }