hdu 1507 Largest Rectangle in a Histogram 动态规划计算最大面积

记录动态规划dpl，dpr，分辨记录i左面的比i大的，右面比i大的，然后(dpr[i]-dpl[i]+1)*h[i]得出长度

动态转移方程while(temp>1 && h[temp-1]>=h[i]) temp=dpl[temp-1]

/*************************************************************************

	> File Name: hdu1506.cpp

	> Author: yang

	> Mail:[email protected]

	> Created Time: 2014年08月24日 星期日 23:41:16

 ************************************************************************/

#include<iostream>

#include<stdio.h>

#include<memory.h>

using namespace std;

#define N 100005

int main(){

	int dpl[N],dpr[N];

	long long h[N];

	int n;

	while(scanf("%d",&n),n){

		for(int i=1;i<=n;i++)

			scanf("%lld",&h[i]);

		dpl[1]=1;

		int temp;

		for(int i=2;i<=n;i++){

			temp=i;

			while(temp>1 && h[temp-1]>=h[i]) temp=dpl[temp-1];

			dpl[i]=temp;

		}

		dpr[n]=n;

		for(int i=n-1;i>=1;i--){

			temp=i;

			while(temp<n && h[i]<=h[temp+1]) temp=dpr[temp+1];

			dpr[i]=temp;

		}

		long long sum,ans=0;

		for(int i=1;i<=n;i++){

//			cout<<dpl[i]<<" "<<dpr[i]<<endl;

			sum=(dpr[i]-dpl[i]+1)*h[i];

//			cout<<"sum:"<<sum<<endl;

			if(sum>ans) ans=sum;

		}

		cout<<ans<<endl;

	}

}