文章目录

I. Max answer

分析

题意: 定义一个区间的值为这个区间最小值乘以区间和
分析：我们要枚举每一个值作为区间最小值时的贡献即可，这样不会漏掉任何情况，但是我们需要统计一个信息，确定了区间最小值，我们还要枚举这个区间，这个区间的最小值已经确定，但是左右边界却不知道，怎么确定左右边界呢？
1.单调栈可以统计一个值作为区间最小值左右端点的信息，不清楚的同学可以先去学习学习单调栈，当它进栈的时候，栈中上一个元素的位置，就是左边界，当它出栈的时候，就是它的右边界
2. 左右边界确定了，怎么在这个范围内求一个最大的区间呢？我们知道区间和可以看成前缀和相减，那么如果,假设左右边界为 l m i n [ i ] + 1 , r m i n [ i ] − 1 lmin[i]+1,rmin[i]-1 lmin[i]+1,rmin[i]−1
3. a [ i ] > 0 a[i] > 0 a[i]>0, 我们需要查询 [ l m i n [ i ] , i − 1 ] [lmin[i],i-1] [lmin[i],i−1]前缀和的最小值， [ i , r m i n [ i ] − 1 ] [i,rmin[i]-1] [i,rmin[i]−1]的前缀和的最大值，这样二者相减才是最大的
4. a [ i ] &lt; 0 a[i] &lt; 0 a[i]<0,我们需要查询 [ l m i n [ i ] , i − 1 ] [lmin[i],i-1] [lmin[i],i−1]前缀和的最大值， [ i , r m i n [ i ] − 1 ] [i,rmin[i]-1] [i,rmin[i]−1]的前缀和的最小值，这样二者相减才是最小的

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 5e5+10;
int a[maxn];
LL dpmx[maxn][19],dpmi[maxn][19],s[maxn];
int lmin[maxn],rmin[maxn],st[maxn];
void initrmq(int n){
	for(int i = 1;i <= n; ++i)
		dpmx[i][0] = s[i],dpmi[i][0] = s[i];
	// cout<<dpmx[2][0]<<endl;
	int x = 0;
	while((1<<(x+1)) <= n) ++x;
	// cout<<x<<endl;
	for(int i = 1;i <= x; ++i){
		for(int j = 1;j+(1<<i)-1 <= n; ++j){
			dpmx[j][i] = -1e18;
			dpmi[j][i] = 1e18;
			dpmx[j][i] = max(dpmx[j][i-1],dpmx[j+(1<<(i-1))][i-1]);
			dpmi[j][i] = min(dpmi[j][i-1],dpmi[j+(1<<(i-1))][i-1]);
			// cout<<i<<" "<<j<<" "<<dpmx[j][i]<<endl;
		}
	}
}
// 传入op = 1 ,表示最小值，op = 0 ，代表最小值

LL rmqquery(int l,int r,int op){
	l++,r++;
	LL _min,_max;
	_min = 1e18;
	_max = -1e18;
	int x = 0;
	while((1<<(x+1)) <= r-l+1)
		++x;
	_min = min(dpmi[l][x],dpmi[r-(1<<x)+1][x]);
	_max = max(dpmx[l][x],dpmx[r-(1<<x)+1][x]);
	return op?_min:_max;
}
int main(void){
	int n;cin>>n;
	for(int i = 1;i <= n; ++i)
		scanf("%d",&a[i]),s[i+1] = s[i]+a[i];
	initrmq(n+1);
	// rmqquery(5,5,0)
	// cout<<s[n]<<endl;
	// cout<< rmqquery(2,n-1,1)<<endl;
	int l = 1,r = 0;
	for(int i = 1;i <= n; ++i){
		while(r >= l&& a[i] < a[st[r]]){
			rmin[st[r]] = i;
			r--;
		}
		lmin[i] = st[r];
		st[++r] = i;
	}
	while(r >= l)
		rmin[st[r]] = n+1,r--;
	// for(int i = 1;i <= n; ++i)
	// cout<<lmin[i]<<" "<<rmin[i]<<endl;
	LL ans = -1e18;
	for(int i = 1;i <= n; ++i){
		LL _m;
		if(a[i] > 0){
			_m = rmqquery(i,rmin[i]-1,0)-rmqquery(lmin[i],i-1,1);
		}
		else{
			_m = rmqquery(i,rmin[i]-1,1)-rmqquery(lmin[i],i-1,0);
			// cout<<rmqquery(i,rmin[i]-1,1)<<" "<<rmqquery(lmin[i],i-1,0)<<endl;
		}
		// cout<<i<<" "<<_m<<endl;
		ans = max(ans,a[i]*_m);
	}
	cout<<ans<<endl;
	return 0;
}