标签：2024.10 minn int 最大值 最小值 maxn ans test 刷题

2024.10.4 test

虹色的北斗七星

思路

题目要求

\[maxn-minn-len \]

的最大值，其中\(maxn\)为区间的最大值,\(minn\)为区间的最小值,\(len\)为区间的长度
注意性质，最优的状态一定是区间的左右端点为最大值和最小值时。因为，如果区间左右端点不为最大值或最小值，那么区间长度就可以继续缩短，所以一定不是最优状态。
此时公式就可以写成

\[a_r-a_l-(r-l+1) \]

或者

\[a_l-a_r-(r-l+1) \]

因为右端点既可以为最大值，也可以为最小值，所以出现了两个公式。
!!!重点
将公式变形就可以得到

\[a_r-r-(a_l-l)-1 \]

或者

\[a_l+l-(a_r+r)-1 \]

于是问题就变成了求最大的\(a[i]-i\)或者是最大的\(a[i]+i\)减去最小的\(a[i]-i\)或者是最小的\(a[i]+i\)
1.钦定当前点\(i\)的\(a[i]-i\)为最大值
求前缀最小值，再带入公式计算
2.钦定当前点\(i\)的\(a[i]+i\)为最小值
求前缀最大值，再带入公式计算

坑点

!!! 当前缀最值是当前点的时候答案为\(-1\),所以\(ans\)最好初始化为\(-INF\)

code

`#include<bits/stdc++.h>

define maxn 4000010

using namespace std;
int a[maxn],n;
int f[maxn],ans=0;
int maxx=0,minn=2147483647;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
f[i]=a[i]+i;
}
for(int i=1;i<=n;i++){
maxx=max(maxx,f[i]);
ans=max(ans,maxx-f[i]);
f[i]=a[i]-i;
}
for(int i=1;i<=n;i++){
minn=min(minn,f[i]);
ans=max(ans,f[i]-minn);
}
cout<<ans-1;
return 0;
}`

标签：2024.10,minn,int,最大值,最小值,maxn,ans,test,刷题
From： https://www.cnblogs.com/GSNforces/p/18446861