hdu 1506 最大子矩阵面积

//写动态规划的题目 要把主要问题提炼出来 这里的问题就是求area=（j-k+1）*a[i]  如果找到j k是解决这个题目的关键 这里暴力求肯定是要超时的 这里用dp来优化

#include<stdio.h>

#include<string.h>

__int64 a[100005],dp[100005],l[100005],r[100005];

int main()

{

   __int64 n,i,t,max;

   while(scanf("%I64d",&n)!=EOF&&n)

   {

      max=-1;

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

         scanf("%I64d",&a[i]);

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

      for(i=2;i<=n;i++)//求每个点左边连续比它大的最左边的下标，保存在l[]数组里

      {

          t=i;

          while(t>1&&a[i]<=a[t-1])

              t=l[t-1];

          l[i]=t;

      }

      for(i=n-1;i>=1;i--)//求每个点右边连续比它大的最右边的下标，保存在r[]数组里

      {

          t=i;

          while(t<n&&a[i]<=a[t+1])

              t=r[t+1];

          r[i]=t;

      }

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

          if((r[i]-l[i]+1)*a[i]>max)

              max=(r[i]-l[i]+1)*a[i];

      printf("%I64d\n",max);

   }

   return 0;

}
巴特西

hdu 1506 最大子矩阵面积

最新文章

热门文章
