poj2796:http://poj.org/problem?id=2796
题意：给出一个长度为n（n<100000）的序列，求出一个子序列，使得这个序列中的最小值乘以这个序列的和的值最大。
思路：枚举每一个点，然后算出以这个点为最小值的区间能向左向右扩展到哪里，然后选择最优的就行。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 const int N=1e5+10; 7 long long a[N]; 8 long long ll[N],rr[N]; 9 long long sum[N]; 10 int n; 11 int main(){ 12 while(~scanf("%d",&n)){ 13 memset(sum,0,sizeof(sum)); 14 memset(ll,0,sizeof(ll)); 15 memset(rr,0,sizeof(rr)); 16 memset(a,-1,sizeof(a)); 17 sum[0]=0; 18 for(int i=1;i<=n;i++){ 19 scanf("%I64d",&a[i]); 20 sum[i]=sum[i-1]+a[i]; 21 } 22 for(int i=1;i<=n;i++){ 23 ll[i]=i; 24 if(i==1)continue; 25 long long t=i-1; 26 while(a[i]<=a[t]){ 27 ll[i]=ll[t]; 28 t=ll[t]-1; 29 } 30 } 31 for(int i=n;i>=1;i--){ 32 rr[i]=i; 33 if(i==n)continue; 34 long long t=i+1; 35 while(a[i]<=a[t]){ 36 rr[i]=rr[t]; 37 t=rr[t]+1; 38 } 39 } 40 long long l,r,ans=-1; 41 for(int i=1;i<=n;i++){ 42 long long temp=a[i]*(sum[rr[i]]-sum[ll[i]-1]); 43 if(temp>ans){ 44 ans=temp; 45 l=ll[i];r=rr[i]; 46 } 47 } 48 printf("%I64d %I64d %I64d ",ans,l,r); 49 } 50 }