Feel Good

Description

Bill is developing a new mathematical theory for human emotions. His recent investigations are dedicated to studying how good or bad days influent people’s memories about some period of life.
A new idea Bill has recently developed assigns a non-negative integer value to each day of human life.
Bill calls this value the emotional value of the day. The greater the emotional value is, the better the daywas. Bill suggests that the value of some period of human life is proportional to the sum of the emotional values of the days in the given period, multiplied by the smallest emotional value of the day in it. This schema reflects that good on average period can be greatly spoiled by one very bad day.
Now Bill is planning to investigate his own life and find the period of his life that had the greatest value. Help him to do so.

Bill 正在开发一种新的人类情感的数学理论。 他最近的研究致力于研究好的或坏的日子是如何影响人们对某段生活的记忆的。 最近，一项新的提案为人类生活的每一天赋予了一个非负整数值。 比尔把这个价值称为当天的情感价值。 情感价值越高，日子就越美好。 比尔认为，人生某个时期的价值与某个时期的情感价值之和成正比，再乘以当天的最小情感价值。 这个模式反映出，平均来说，好的时间段可能会被糟糕的一天大大破坏。 现在比尔正计划调查他自己的生活，找出他生命中最有价值的时期。 帮他这么做。
Input

The first line of the input contains n - the number of days of Bill’s life he is planning to investigate(1 <= n <= 100 000). The rest of the file contains n integer numbers a1, a2, … an ranging from 0 to 106 - the emotional values of the days. Numbers are separated by spaces and/or line breaks.

输入的第一行包含了 n-bill 计划调查的生命天数(1n100000)。 文件的其余部分包含 n 个整数 a1，a2… … 范围从0到106——每天的情绪值。 数字由空格和 / 或换行符分隔。
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 r such that the period from l-th to r-th day of Bill’s life(inclusive) has the greatest possible value. If there are multiple periods with the greatest possible value,then print any one of them.

在第一行印出比尔生命中某段时期的最大价值。 在第二行打印两个数字 l 和 r，使得从比尔生命的第一天到第二天(包括在内)的时间段具有最大的可能值。 如果有多个最大可能值的周期，那么打印其中的任何一个。
Sample Input

6
3 1 6 4 5 2
Sample Output

60
3 5

题意分析

n个数，求某段区间的最小值*该段区间所有元素之和的最大值

解题思路

用 前缀和 和 单调栈
找到当前值在哪些区间中为最小值，找到最左端和最右端
再用前缀和知道这个区间的和
利用a[i]*(f[r[i]]-f[l[i-1]])公式更新最大值

注意：最左端和最右端的初值要为1
否则当输入1 0时会输出0 0 0这个错误的答案

AC代码

#include<cstdio>
#include<iostream>
using namespace std;
long long n,s,sl=1,sr=1,tail,a[100005],l[100005],r[100005],f[100005],p[100005];
int main()
{
   
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
     {
   
    	scanf("%d",&a[i]);
     	f[i]=f[i-1]+a[i];//前缀和
        l[i]=r[i]=i;//初值
     }
    for(int i=1;i<=n;i++)//找最左端
     {
   
     	while(a[i]<=a[p[tail]]&&tail>=1)
     	{
   
     	 	l[i]=l[p[tail]];
		    tail--;
     	}
     	p[++tail]=i;
     }
    tail=0;//清零
    for(int i=n;i>=1;i--)//找最右端
     {
   
     	while(tail!=0&&a[i]<=a[p[tail]])
     	 {
   
     	  	r[i]=r[p[tail]];
		   	tail--;
     	 }
     	p[++tail]=i;
     }
    for(int i=1;i<=n;i++)//找最大值
     if(a[i]*(f[r[i]]-f[l[i]-1])>s)
     {
   
     	s=a[i]*(f[r[i]]-f[l[i]-1]);
        sl=l[i];
	    sr=r[i];	
     }
    cout<<s<<endl<<sl<<" "<<sr;
}

谢谢