题解
知识点：贪心，前缀和，枚举。
首先考虑一个贪心结论，选择区间端点一定是两个最大值，因此 \(i_1 = l,i_3 = r\) 。
考虑变形式子 \((b_l + l) + b_{i_2} + (b_r - r)\) ，那我们枚举 \(b_{i_2}\) 只需要知道 \(\{ b_i + i \}\) 的前缀最大值，和 \(\{ b_i - i \}\) 的后缀最大值即可。
注意，这样得到的 \(b_{i_2}\) 不一定是真正的 \([l,r]\) 内的 \(b_{i_2}\) ，但可以肯定的是这样不影响最优解。
时间复杂度 \(O(n)\)
空间复杂度 \(O(n)\)
代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int a[100007];
int pre[100007], suf[100007];
bool solve() {
int n;
cin >> n;
for (int i = 1;i <= n;i++) {
cin >> a[i];
pre[i] = a[i] + i;
suf[i] = a[i] - i;
}
suf[n + 1] = -n - 1;
for (int i = 1;i <= n;i++) pre[i] = max(pre[i], pre[i - 1]);
for (int i = n;i >= 1;i--) suf[i] = max(suf[i], suf[i + 1]);
int ans = 0;
for (int i = 1;i <= n;i++) ans = max(ans, pre[i - 1] + a[i] + suf[i + 1]);
cout << ans << '\n';
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}