题意
给你一个长度为 \(n\) 的序列 \(b\)，求下面这个式子的值：
\[\max_{1 \le l \le i \lt j \lt k \le r \le n}(b_i + b_j + b_k -(r - l))
\]
\(n \le 10^5\)。
思路
官方题解给出的做法使用了单调栈，这里给出一种不用栈的做法。
首先，把题目的柿子优化下。显然，为了尽量地减小 \(r - l\) 的值，我们直接令 \(i = l\)，\(k = r\)。于是有：
\[\begin{aligned}
\mathrm{ans} &= \max_{1 \le l \le i \lt j \lt k \le r \le n}(b_i + b_j + b_k -(r - l)) \\
&= \max_{1 \le i \lt j \lt k \le n}(b_i + b_j + b_k - (k - i)) \\
&= \max_{1 \le i \lt j \lt k \le n}(b_j + (b_i + b_k) - (k - i)) \\
&= \max_{1 \le i \lt j \lt k \le n}(b_j + (b_i - (j - i)) + (b_k - (k - j))) \\
&= \max_{1 \lt j \lt n}(b_j + \max_{1 \le i \lt j}(b_i - (j - i)) + \max_{j \lt k \le n}(b_k - (k - j)))
\end{aligned}
\]
然后做法其实就比较显然了。对于每一个 \(j \in [2, n - 1]\)，把 \(b_i - (j - i)\) 与 \(b_k - (k - j)\) 的最大值预处理出来，再扫一遍取最大值，就可以得到答案。
暴力预处理是 \(O(n^2)\) 的，但其实预处理可以通过 \(O(n)\) 递推实现，不妨设 \(f_j = \max_{1 \le i \lt j}(b_i - (j - i))\)，不难看出 \(f\) 单调不减。假设已经得到了 \(f_{j - 1}\)，由于 \(f\) 的单调性，\(f_j\) 有两种可能：
- \(f_j\) 对应的 \(i\) 与 \(f_{j - 1}\) 对应的 \(i\) 相同，再减掉一个坐标的增量，即 \(f_j = f_{j - 1} - 1\)；
- \(f_j\) 对应的 \(i\) 为 \(j - 1\)，则 \(f_j = b_{j - 1} - (j - (j - 1)) = b_{j - 1} - 1\)。
为什么只可能是这两种决策呢？因为 \(f\) 是具有单调性的，设 \(f_{j - 1}\) 对应的 \(i\) 值为 \(x\)，如果存在 \(y \in [1, j - 1)\) 且 \(x \neq y\) 使得 \(y\) 为 \(f_j\) 对应的 \(i\) 的话，则有：
\[\begin{aligned}
b_y - (j - y) &\ge b_x - (j - x) \\
b_y - ((j - 1) - y) &\ge b_x - ((j - 1) - x) \\
b_y - ((j - 1) - y) &\ge f_{j - 1} \\
\end{aligned}
\]
而这与 \(x\) 为 \(f_{j - 1}\) 对应的 \(i\) 相矛盾，因为选择 \(y\) 比选择 \(x\) 更优。
\(\max_{j \lt k \le n}(b_k - (k - j))\) 的预处理同理，同样可以做到 \(O(n)\)。于是总的时间复杂度为 \(O(n)\)。
代码
#include <bits/stdc++.h>
using i64 = long long;
using i64u = unsigned long long;
using f80 = long double;
void solve() {
int n;
std::cin >> n;
std::vector<int> b(n);
for (int i = 0; i < n; i++) {
std::cin >> b[i];
}
std::vector f(2, std::vector<int>(n));
for (int i = 1; i < n; i++) {
f[0][i] = std::max(f[0][i - 1], b[i - 1]) - 1;
}
for (int i = n - 2; i >= 0; i--) {
f[1][i] = std::max(f[1][i + 1], b[i + 1]) - 1;
}
int ans = 0;
for (int i = 1; i < n - 1; i++) {
ans = std::max(ans, f[0][i] + f[1][i] + b[i]);
}
std::cout << ans << "\n";
return;
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int t;
std::cin >> t;
while (t--) {
solve();
}
return 0;
}