#include<iostream> using namespace std; #define MAX 100010 //用你自己的思维解决问题 long long v[MAX],height[MAX],dp[MAX],maxn; int main(){ int n; while(cin>>n){ if(n==0) break; memset(height,0,sizeof(height)); memset(dp,0,sizeof(dp)); memset(v,0,sizeof(v)); for(int i=0;i<n;i++) cin>>height[i]; dp[0]=height[0]; v[0]=height[0]; for(int i=1;i<n;i++){ if(v[i-1]>height[i]){//连成一片截别人 v[i]=height[i]; dp[i]=(dp[i-1]/v[i-1]+1)*height[i]; } else { //连成一片截自己 if(dp[i-1]+v[i-1]>=height[i]){ v[i]=v[i-1]; dp[i]=dp[i-1]+v[i]; } else{ // 自己独成一片 v[i]=height[i]; dp[i]=height[i]; } } } maxn=0; for(int i=0;i<n;i++){ if(dp[i]>maxn) maxn=dp[i]; } cout<<maxn<<endl; } return 0; }
觉得自己挺对的，一般测试数据都能过，但是没有A，到底是哪里出了问题，理一下思路吧
要找出最大子矩阵，那么对于当前这块木板，
1）如果它比左边的矩阵的高度短，那么肯定是截取左边的矩阵，使其高度和自己一样高
2）如果它比左边矩阵的高度大的话，那么可以考虑截取自己的高度，和左边矩阵的高度一样，还是自己独立成为一个新的矩阵
有一种思路是对于每个单位矩阵，求每个矩形向2边延伸的最大长度，用2个数组来记录，l[i]，表示第i个矩形左边的最大下标，
r[i] ，表示第i个矩阵右边的最大下标。
这样每个人矩阵的面积就可以为
S[i]=(r[i]-l[i]+1)*height[i];
最后求出最大的s[i];
感觉这种思维比起我的，更宏观一点，突然发现我的思维是有问题的，在第一点那个地方，如果所谓的左边的那个矩阵的左边的高度比当前这个还大呢，那样我们就可以一同截取了，所以我的思维是错误的。不好意思~~，算法就是让我们的思维更加缜密~~
那么如何找到l[i]呢，一个一个地比较吗？这时动规排上了用场
右扫一遍，求出每个点的l保存在l[]数组里，然后从右到左扫一遍，求出每个点的r保存在r[]数组里，最后可以求出最大的矩阵了。
利用动态规划,如果它左边高度大于等于它本身,那么它左边的左边界一定满足这个性质,再从这个边界的左边迭代下去
正确代码：
#include<iostream>
using namespace std;
#define MAX 100010
//用你自己的思维解决问题
long long height[MAX],l[MAX],r[MAX],maxn,S[MAX];
int main(){
int n;
long long t;
while(cin>>n){
if(n==0) break;
memset(height,0,sizeof(height));
memset(l,0,sizeof(l));
memset(r,0,sizeof(r));
memset(S,0,sizeof(S));
for(int i=1;i<=n;i++)
cin>>height[i];
l[1]=1;r[n]=n;
for(int i=2;i<=n;i++)//求每个点左边连续比它大的最左边的下标，保存在l[]数组里
{
t=i;
while(t>1&&height[i]<=height[t-1])
t=l[t-1];
l[i]=t;
}
for(int i=n-1;i>=1;i--)//求每个点右边连续比它大的最右边的下标，保存在r[]数组里
{
t=i;
while(t<n&&height[i]<=height[t+1])
t=r[t+1];
r[i]=t;
}
maxn=0;
for(int i=1;i<=n;i++){
S[i]=(r[i]-l[i]+1)*height[i];
if(S[i]>maxn)
maxn=S[i];
}
cout<<maxn<<endl;
}
return 0;
}
：
原文：http://www.cnblogs.com/wintersong/p/4982945.html