Question

用c++编程求矩形最大面积

题目详情
给定直方图，每一小块的height由N个非负整数所确定，每一小块的width都为1，请找出直方图中面积最大的矩形。

如下图所示，直方图中每一块的宽度都是1，每一块给定的高度分别是[2,1,5,6,2,3]：

那么上述直方图中，面积最大的矩形便是下图所示的阴影部分的面积，面积= 10单位。

设有1000个矩形，求出最大面积。

如输入 6
输出
1 2 3 4 5 6
最大面积为
10
补充下，只看最大的两个矩形





Answer 1

哥们是12好吧
1 2 3 4 5 6
4 5 6-》4+4+4=12
这就是求相邻的连续数字的最大和（相邻数字求和变成，相邻数最小*相邻个数）
最大和为 0个相邻的最大，1个相邻的最大，。。。n-1个相邻的最大
1 2 3 4 5 6
0个最大的是：6
1个最大的是5 6-》5+5
2个最大是：4 5 6 -》4+4+4
。。。遍历到n-1个最大
在从n-1个最大求个最大就是结果
若是只看两个最大：
就更简单了：
两个两个求下相邻和：结果保存到另一个数组
求该数组中的最大数

追问

具体题目我忘了 好像是只要求最大的两个矩形的面积

追答

#include <iostream>
using namespace std;
int max2(int a[],int leng)
{
int b[1000],i,max=0;
for (i=0;i<leng-1;i++)
{
b[i]=a[i]+a[i+1]-abs(a[i]-a[i+1]);
if (max<b[i])
{
max=b[i];
}
}
return max;
}
void main()
{
int n,m,a[1000];
cin>>n;
for (int i=0;i<n;i++)
{
cin>>a[i];
}
m=max2(a,n);
cout<<m<<endl;
}

追问

能输入一个N，自己显示1-n么 而不是自己输入每个数

追答

//自己输入n个数，随机数生成
#include <stdlib.h>
#include <time.h> 
#include <iostream>
using namespace std;
int max2(int a[],int leng)
{
int b[1000],i,max=0;
for (i=0;i<leng-1;i++)
{
b[i]=a[i]+a[i+1]-abs(a[i]-a[i+1]);
if (max<b[i])
{
max=b[i];
}
}
return max;
}
void main()
{
 srand((unsigned)time(NULL)); 
int n,m,a[1000];
cin>>n;
for (int i=0;i<n;i++)
{
a[i]=rand()%100;
}
for (int i=0;i<n;i++)
{
cout<<a[i]<<" ";
}
m=max2(a,n);
cout<<endl<<m<<endl;
}

追问

额 不算随机生成的 是从1开始的= = 顺序是随机的 比如10个数 2 6 4 3 1 5 7 9 8 10

追答

不重复的随机数？

追问

嗯 比如输入10 那就出现高为1-10的矩形，但是1-10不是按顺序排列的（题目有点忘了）

追答

#include <stdlib.h>
#include <time.h> 
#include <iostream>
using namespace std;
int max2(int a[],int leng)
{
int b[1000],i,max=0;
for (i=0;i<leng-1;i++)
{
b[i]=a[i]+a[i+1]-abs(a[i]-a[i+1]);
if (max<b[i])
{
max=b[i];
}
}
return max;
}
void main()
{
 srand((unsigned)time(NULL)); 
int n,m,a[1000];
cin>>n;
for (int i=0;i<n;i++)
{
a[i]=rand()%n+1;//  数字是1-n的
}
for (int i=0;i<n;i++)
{
cout<<a[i]<<" ";
}
m=max2(a,n);
cout<<endl<<m<<endl;
}

追问

能不能改成每个数都不重复呢

追答

#include <stdlib.h>
#include <time.h> 
#include <iostream>
using namespace std;
int max2(int a[],int leng)
{
int b[1000],i,max=0;
for (i=0;i<leng-1;i++)
{
b[i]=a[i]+a[i+1]-abs(a[i]-a[i+1]);
if (max<b[i])
{
max=b[i];
}
}
return max;
}
void  fun( int  *a,int num)
{ int  i, x, n=0;
x=rand()%num+1;                            //   产生小于20的随机数
/**********found**********/            
while (n<num)
{  for(i=0; i<n; i++ )//如上i是<n,但是之到i=n跳出循环，此时i=n
/**********found**********/
if( x==a[i] ) break;
/**********found**********/
if( i==n){ a[n]=x; n++; }                
x=rand()%num+1;
}
}
void main()
{
 srand((unsigned)time(NULL)); 
int n,m,a[1000],j=1,t;
cin>>n;
fun(a,n);
for (int i=0;i<n;i++)
{
cout<<a[i]<<" ";
}
m=max2(a,n);
cout<<endl<<m<<endl;
}