#PROBLEM LINK:
Author: Ayush Nagal
#DIFFICULTY:
EASY-MEDIUM
#PROBLEM:
Given an array a containing n elements. We have to find the largest solid area in which the mall can be constructed.
There are a number of buildings in a certain two-dimensional landscape. Each building has a height, given by h[i] where 1 \leq i \leq n. If you join k adjacent buildings, they will form a solid rectangle of area \text{ k x min(h[i], h[i+1], ......, h[i+k-1])}.
#EXPLANATION:
This problem can be easily solved in O(n^2). We need to run 2 nested for loops as shown below:
for(long int i=0;i<n;i++)
{
m=a[i];
for(long int j=i+1;j<n;j++)
{
if(m>a[j])
m=a[j];
if(m*(j-i+1)>max)
max=m*(j-i+1);
}
}
Here, m is to store the minimum height in the range [i,j]. max is used to store the maximum area that can be formed.
#AUTHOR’S SOLUTION:
Author’s solution can be found here.