POJ 2796 Feel Good【単調なスタック＋プレフィックスと非負の区間の最小値乗組区間と】

Feel Good
Time Limit: 3000 MS
 
メモリLimit: 65536 K
Total Submissions: 20284
 
Acceepted: 5597
Case Time Limit: 1000 MS
 
Special Jundge
Description
Bill is developing a new mathematical theory for hman eotions.His recent investigations are dedicated to studying how good or bad days influnt people's memories aboot some period of life.  A new idea Bill has recently developed assigns a non-negative integer value to each day of hman life.  Bill cars this value the emotional value of the day.The greater the emationl value is,the better the days.Bill suggas Stat the value of some period of huoman life is proportional to the sum of the emotion vance daysmultipled by the smalest emational value of the day in it.This schema reflectthat good on average period can be greatly spoled by one very bad day.  Now Bill is planing to investigate his own life and find the period of his life that had the greatest value.Help hit to do so.
Input
The first line of the input contains n-the number of days of Bill's life he is planing to investigate(1==n==100,000)The ret of the file contains n integer numbers a 1,a 2,…randing from 0 to 106 - the emotional values of the days.Numbers are separated by spaces and/or line breaks.
Output
Print the greatest value of some period of Bill's life in the first line.And on the second line print two numbers l and such that the period from l-th to r-th day of Bill's life(inclive)has the the grease the the part varse.the part bles.the.
Sample Input

6
3 1 6 4 5 2

Sample Output

60
3 5

ソurce
Northeastern Europe 2005
題意
負ではない配列を指定して、区間の最小値と最大値を求めて、この最大値を出力し、対応する左右閉区間の端点値を記録します.複数の区間があれば、いずれかを出力します.
考え方
非負の配列であるため、その区間が大きいほど、その区間と才能が大きくなり、各数を列挙し、単調なスタックを使って計算し、それを最小値として左へ右へ拡張する最大区間で、絶えず解答を更新すればいいです.
C++コード

#include

using namespace std;

const int N=100005;

typedef long long ll;

ll sum[N];
int a[N],L[N],s[N],l,r;

int main()
{
	int n;
	while(~scanf("%d",&n))
	{
		sum[0]=0;
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
			L[i]=i;
			sum[i]=sum[i-1]+a[i];
		}
		a[n+1]=-1;//       ，        
		int top=0;
		ll ans=-1;
		//          
		for(int i=1;i<=n+1;i++)
		{
			while(top>0&&a[s[top]]>a[i])
			{
				ll temp=(sum[i-1]-sum[L[s[top]]-1])*a[s[top]];
				if(ans0&&a[s[top]]==a[i]) L[i]=L[s[top]];
			s[++top]=i;
		}
		printf("%lld
%d %d
",ans,l,r);
	}
	return 0;
}