Alice has a magic array. She suggests that the value of a interval is equal to the sum of the values in the interval, multiplied by the smallest value in the interval.
Now she is planning to find the max value of the intervals in her array. Can you help her?
Input
First line contains an integer n(1 \le n \le 5 \times 10 ^5n(1≤n≤5×105).
Second line contains nn integers represent the array a (-10^5 \le a_i \le 10^5)a(−105≤ai≤105).
Output
One line contains an integer represent the answer of the array.
样例输入复制
5
1 2 3 4 5
样例输出复制
36
编辑代码
题意：
给你n个数字a[1~n]（a[i]可能为负的），求任意一段区间和乘以区间数的最小值，求其最大。
分析：
我们枚举每一个a[i],寻找a[i]的可以满足的左右区间【l,r】。
l[i]左边第一个<h[i]的位置
r[i]右边第一个<h[i]的位置运用单调栈或者DP都可以求，如果没有负数则就是：【POJ-2796】Feel Good
这题的难点是有负数，
如果h[i]>0,则直接求出h[i] * (sum[r[i]] - sum[l[i] - 1]);（因为正数的合法区间不会有负数）
如果h[i]<0,我们暴力寻找左边的sum[i]的最大值，寻找右边的sum[i]的最小值即可
单调栈做法
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf=1e18;
const int N = 500050;
ll h[N],sum[N];
ll l[N];//l[i]左边第一个<h[i]的位置
ll r[N];//r[i]右边第一个<h[i]的位置
int main()
{
int n;
stack<int> s;
while(~scanf("%d",&n))
{
if(n==0) return 0;
for(int i=1;i<=n;i++)
{
scanf("%lld",&h[i]);
sum[i]=sum[i-1]+h[i];
}
while(s.size()) s.pop();
for(int i=1;i<=n;i++)//保存单调递减栈（栈顶元素最小）
{
while(!s.empty()&&h[s.top()]>=h[i])
s.pop();
if(s.empty()) l[i]=1;
else l[i]=s.top()+1;
s.push(i);
}
while(s.size()) s.pop();
for(int i=n;i>=1;i--) //保存单调递减栈（栈顶元素最小）
{
while(!s.empty()&&h[s.top()]>=h[i])
s.pop();
if(s.empty()) r[i]=n;
else r[i]=s.top()-1;
s.push(i);
}
ll ans = -1e9;
for(int i = 1; i <= n; i++)
{
ll t;
if(h[i]>=0)
{
t = h[i] * (sum[r[i]] - sum[l[i] - 1]);
}
else
{
ll minn=inf,maxx=-inf;
for(int j=l[i]-1; j<i; j++)
{
maxx=max(sum[j],maxx);
}
for(int j=i; j<=r[i]; j++)
{
minn=min(sum[j],minn);
}
t=h[i]*(minn-maxx);
}
ans=max(t,ans);
}
printf("%lld\n", ans);
}
return 0;
}
DP
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <vector>
using namespace std;
typedef long long ll;
const ll inf=1e18;
const int N=500005;
ll h[N];
ll l[N],r[N],sum[N];
//l[i]左边连续的>=a[i]位置
//r[i]右边连续的>=a[i]位置
int main()
{
int n;
while(scanf("%d",&n)!=-1)
{
if(n==0)
break;
stack<ll>s;
sum[0]=0;
for(int i=1; i<=n; i++)
{
scanf("%lld",&h[i]);
sum[i]+=sum[i-1]+h[i];
}
sum[n+1]=sum[n];
h[n+1]=0; ///注意这里
for(int i=1; i<=n+1; i++)
{
while(!s.empty()&&h[s.top()]>h[i])
{
r[s.top()]=i;
s.pop();
}
if(s.size()==0)
l[i]=i;
else
l[i]=s.top();
s.push(i);
}
ll ans = -1e9;
for(int i = 1; i <= n; i++)
{
ll t;
if(h[i]>=0)
{
t = h[i] * (sum[r[i]] - sum[l[i] - 1]);
cout<<r[i]<<" "<<l[i]<<endl;
}
else
{
ll minn=inf,maxx=-inf;
for(int j=l[i]-1; j<i; j++)
{
maxx=max(sum[j],maxx);
}
for(int j=i; j<=r[i]; j++)
{
minn=min(sum[j],minn);
}
t=h[i]*(minn-maxx);
}
ans=max(t,ans);
}
printf("%lld\n", ans);
}
return 0;
}
//DP+线段树
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf=1e18;
const int N = 5000050;
ll h[N],sum[N];
ll l[N];//l[i]左边第一个<h[i]的位置
ll r[N];//r[i]右边第一个<h[i]的位置
#define lson i<<1
#define rson i<<1|1
#define LS l,mid,lson
#define RS mid+1,r,rson
#define ll long long
ll b[N];
ll ans_sum,ans_max,ans_min;
struct node
{
int l,r;
ll max,min;
} tree[N<<2];
void pushup(int i)
{
tree[i].max=max(tree[lson].max,tree[rson].max);
tree[i].min=min(tree[lson].min,tree[rson].min);
}
//建立线段树
void build(int l,int r,int i)
{
tree[i].l = l;
tree[i].r = r;
if(l == r)
{
tree[i].max = sum[l];
tree[i].min = sum[l];
return;
}
int mid = (l+r)>>1;
build(LS);
build(RS);
pushup(i);
}
void query(int l,int r,int i)
{
//cout<<l<<" "<<r<<" "<<i<<endl;
if(l <= tree[i].l && tree[i].r <= r)
{
ans_max = max(ans_max,tree[i].max);
ans_min = min(ans_min,tree[i].min);
return ;
}
// pushdown(i);
int mid = (tree[i].l+tree[i].r)>>1;
if(l<=mid) query(l,r,lson);
if(r>mid) query(l,r,rson);
pushup(i);
}
stack<int> s;
int main()
{
int n;
while(~scanf("%d",&n))
{
for(int i=1; i<=n; i++)
{
scanf("%lld",&h[i]);
}
for(int i=1;i<=n;i++)
{
scanf("%lld",&b[i]);
sum[i]=sum[i-1]+b[i];
}
build(1,n,1);
while(s.size())
s.pop();
for(int i=1; i<=n; i++) //保存单调递减栈（栈顶元素最小）
{
while(!s.empty()&&h[s.top()]>=h[i])
s.pop();
if(s.empty())
l[i]=1;
else
l[i]=s.top()+1;
s.push(i);
}
while(s.size())
s.pop();
for(int i=n; i>=1; i--) //保存单调递减栈（栈顶元素最小）
{
while(!s.empty()&&h[s.top()]>=h[i])
s.pop();
if(s.empty())
r[i]=n;
else
r[i]=s.top()-1;
s.push(i);
}
ll ans = -1e18;
for(int i = 1; i <= n; i++)
{
ll t;
if(h[i]>=0)
{
t = h[i] * (sum[r[i]] - sum[l[i] - 1]);
}
else
{
ll minn=inf,maxx=-inf;
ans_max=-1e18;
query(l[i]-1,i-1,1);
maxx=ans_max;
ans_min=1e18;
query(i,r[i],1);
minn=ans_min;
t=h[i]*(minn-maxx);
}
ans=max(t,ans);
}
printf("%lld\n", ans);
}
return 0;
}
标签：max,int,Max,ll,tree,2019,ans,answer,sum From： https://blog.51cto.com/u_14932227/6041851