poj2796:

题意：给出一个长度为n（n<100000）的序列，求出一个子序列，使得这个序列中的最小值乘以这个序列的和的值最大。

思路：枚举每一个点，然后算出以这个点为最小值的区间能向左向右扩展到哪里，然后选择最优的就行。

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           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\n%I64d %I64d\n",ans,l,r);49    }50 }