hdu-1506

DPa[i]의 왼쪽과 오른쪽이 자신보다 큰 수의 길이와 연결되어 있는 것을 찾아내고 이 길이에 a[i]를 곱하면 가장 큰 곱셈이 답이다

#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include   
#include   
#include  

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

hdu-1506

좋은 웹페이지 즐겨찾기