poj 2796

---

原题

题意：

给定一个长度为 n(n<105) 的非负整数序列 a ，定义函数f(l,r)=(minri=la[i])∗(∑ri=la[i])，求 f(l,r) 的最大值及其对应的 l 与r

思路：

对于 ∑ri=l(a[i]) 可以通过前缀和相减 O(1) 得到。 当最小值 a[i] 确定时，由于序列 a 是非负整数序列，区间越大sum值越大，故我们希望在保证 a[i] 是区间最小值的同时使得区间长度 r−l+1 尽可能大，这里可以用单调栈处理。 枚举每个点为区间最小值，取所有情况的最大值，复杂度 O(n) 。 注意答案会爆int。

单调栈：

# include<stdio.h> const int NMax=100000; int n, ansL, ansR, in[NMax+1], range[NMax+1][2]; long long sum[NMax+1], ans; struct Stack{ int id[NMax+1]; int top; void Init(){top=0;} void Pop(){top--;} void Push(int i){id[top++]=i;} bool Empty(){return top==0;} int Head(){return id[top-1];} }sta; int main(){ int i; scanf("%d", &n); ans=(1<<31); sum[0]=0; sta.Init(); for(int i=1; i<=n; i++){ scanf("%d", in+i); sum[i]=sum[i-1]+in[i]; } for(int i=1; i<=n; i++){ while(!sta.Empty() && in[sta.Head()]>=in[i]){ range[sta.Head()][1]=i-1; sta.Pop(); } range[i][0]=sta.Empty()?1:sta.Head()+1; sta.Push(i); } while(!sta.Empty()){ range[sta.Head()][1]=n; sta.Pop(); } for(int i=1; i<=n; i++){ long long tans; tans=(sum[range[i][1]]-sum[range[i][0]-1])*in[i]; if(tans>ans){ ans=tans; ansL=range[i][0]; ansR=range[i][1]; } } printf("%lld\n%d %d\n", ans, ansL, ansR); return 0; }