这篇文章上次修改于 698 天前，可能其部分内容已经发生变化，如有疑问可询问作者。
题意：
你有一个长度为 $n$ 的序列 $a$，它的一个区间 $[l,r]$ 的价值是 $\max\{a_l,a_{l+1},\cdots,a_r\}-\min\{a_l,a_{l+1},\cdots,a_r\}-r+l-1$。求这个序列价值最大的子区间并输出这个价值。
为什么又是区间
看到区间的题，有一种非常常用的方法是枚举右端点，确定左端点。这道题也不例外。
举个栗子：求区间最大值，我的做法是记录前面前缀和的最大值，再用当前的前缀和减前面的前缀和更新答案。
代码片段（非本题）：
ans=0;
_min=0;
for(int i=1;i<=n;i++){
now+=a[i];
_min=min(_min,now);
ans=max(ans,now-_min);
}这个算法将答案分成两部分，分别是前面的前缀和以及后面的前缀和。
回到本题，先对式子一顿折腾：$(\max\{a_l,a_{l+1},\cdots,a_r\}+l)-(\min\{a_l,a_{l+1},\cdots,a_r\}+r+1)$没有太折腾
再分析一下题，区间的端点应该在最大值和最小值上，因为他要是区间越小越好。
假设说最小值的端点在右边，那么在前面找到$\max\{a_l,a_{l+1},\cdots,a_r\}+l$的最大值，再减去$\min\{a_l,a_{l+1},\cdots,a_r\}+r+1$，为什么是这样的？
因为一旦确定最小值就相当于$\min\{a_l,a_{l+1},\cdots,a_r\}+r+1$已经被确定了。那只要让$\max\{a_l,a_{l+1},\cdots,a_r\}+l$（被减数 ）最大。
最小值的端点在左边怎么办？
翻转一遍就好了。
#include <iostream>
#include <cstdio>
#include <algorithm>
#define int long long
using namespace std;
inline int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){
c=='-'?f=-1:1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=(x<<3)+(x<<1)+(c^48);
c=getchar();
}
return f*x;
}
int a[4000005];
signed main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
int n=read();
int ans=0;
int mx=-1,re=-1;
for(int i=1;i<=n;i++){
a[i]=read();
mx=max(mx,a[i]+i);
re=max(re,mx-a[i]-i-1);
}
reverse(a+1,a+n+1);
mx=-1;
for(int i=1;i<=n;i++){
mx=max(mx,a[i]+i);
re=max(re,mx-a[i]-i-1);
}
printf("%lld",re);
return 0;
}