BC105 - Editorial

easy-medium
editorial
loop
maths

#1

#PROBLEM LINK:

Practice
Contest

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.