学步园

DP 找出 a[i] 的左边和右边与自己连着的比自己大的数的长度 , 然后用这个长度乘以 a[i], 乘积最大的那个就是答案 

#include<stdio.h>  
#include<iostream>  
#include<math.h>  
#include<stdlib.h>  
#include<ctype.h>  
#include<algorithm>  
#include<vector>  
#include<string.h>  
#include<queue>  
#include<stack>  
#include<set>  
#include<map>  
#include<sstream>  
#include<time.h>  
#include<utility>   
#include<malloc.h>   
#include<stdexcept>  

using namespace std;

int n;
long long  a[100010];
long long  l[100010],r[100010];
int main()
{
    while (scanf ("%d",&n)!=EOF && n)
    {
        for (int i=1 ;i<=n;i++)
            scanf ("%I64d",&a[i]);

        l[1]=1;
        r[n]=n;

        for(int i=2 ;i<=n;i++)
        {
            int t=i;
            while (t>1 && a[i]<=a[t-1])
                t=l[t-1];
            l[i]=t;
        }
        for(int i=n-1;i>=1;i--)
        {
            int t=i;
            while(t<n && a[i]<=a[t+1])
                t=r[t+1];
            r[i]=t;
        }
        long long  ans =0;
        for (int i=1 ;i<=n;i++)
        {
            ans = max (ans ,(r[i]-l[i]+1)*a[i]);
        }
        printf("%I64d\n",ans);
    }
    return 0;
}