hdu 1506 Largest Rectangle in a Histogram(求最大的矩形)

1.注意要把a[]定义为LL，我在这里wa了N次

2.寻找边界时，得用dp思想

AC代码：

#include
  
   
#include
   
     #define LL long long using namespace std; const LL INF=1<<60; LL a[100005];//要定义为LL int L[100005]; int R[100005]; int main() { int n; while(scanf("%d",&n),n) { for(int i=1;i<=n;i++) { scanf("%lld",&a[i]); } for(int i=1;i<=n;i++)//用dp思想，不断地扩展边界 { L[i]=i; while(L[i]>1&&a[L[i]-1]>=a[i]) L[i]=L[L[i]-1]; } for(int i=n;i>=1;i--) { R[i]=i; while(R[i]
    
     =a[i]) R[i]=R[R[i]+1]; } LL ans=-INF; for(int i=1;i<=n;i++) { LL temp=a[i]*(R[i]-L[i]+1); if(ans
     
      没用dp思想找边界的超时代码：
      
?






      
?
      
#include
       
        
#include
        
          #define LL long long using namespace std; const LL INF=1<<60; LL a[100005]; int L[100005]; int R[100005]; int main() { int n; while(scanf("%d",&n),n) { for(int i=1;i<=n;i++) { scanf("%lld",&a[i]); } for(int i=1;i<=n;i++)//超时，得用dp思想优化 { int j=i; while(j>1&&a[j]>=a[i]) j--; L[i]=++j; } for(int i=1;i<=n;i++) { int j=i; while(j
         
          =a[i]) j++; R[i]=--j; } LL ans=-INF; for(int i=1;i<=n;i++) { LL temp=a[i]*(R[i]-L[i]+1); if(ans
          
           
?