Largest Rectangle Area Solution || Chefland Histogram's Bar || Chef Area of Largest Rectangle Solution ||

Largest Rectangle Area:

Problem

In Chefland there are $N$ bars representing the histogram's bar and the width of each bar is $1$. Now Chef wants to find the area of the largest rectangle. Help Chef to find the maximum possible value. Note that you can't rearrange or move any of the bars.

Input

• The first line of each test case contains a single integer $N$.
• The second line contains $N$ space-separated integers $A_1, A_2, \ldots, A_N$.

Output

Print a single line containing one integer — the area of the largest rectangle.

Constraints

• $1\; \backslash leq\; T\; \backslash leq\; 10$
• $1 \leq N \leq 10^5$
• $1 \leq A_i \leq 10^9$ for each valid $i$

Example:

Input:

4

2 2 5 6

Output:

10

Explanation:

We can find the largest rectangle from the last 2 bars, so 5+5=10.

Sample Input:

6
4 3 5 7 2 1

Sample Output:

12

Explanation

Example case 1: We can find the largest rectangle from the last $2$ bars, so $5 + 5 = 10$.

Example case 2: We can find the largest rectangle from the first $4$ bars, so $3 + 3 + 3 + 3 = 12$.

Program :

#C

 #include<stdio.h>

long int max(long int a1,long int a2)

{

    if( a1 > a2 )

        return a1;

    else

        return a2;

}

long int Area1(long h[], int s, int e) 

{

   long int max_Area=0;

   if ( s > e )

   return 0;

   int min_index=s;

   for(int i=s ; i <= e ; i++)

   if(h[min_index] > h[i])

   min_index = i;

   max_Area=max(h[min_index] * (e-s+1),

   max(Area1(h , s, min_index-1),

   Area1(h ,min_index+1 ,e)));

   return max_Area;

}

int main()

{

  int n , j;

    scanf("%d", &n);

    long a[n];

    for(j=0 ; j < n ; j++)

      scanf("%ld", &a[j]);

    printf("%ld\n", Area1(a,0,n-1));

}

#Python

def max(a1, a2):

    if a1 > a2:

        return a1

    else:

        return a2

def Area1(h, s, e):

    max_Area = 0

    if s > e:

        return 0

    min_index = s

    for i in range(s, e+1):

        if h[min_index] > h[i]:

            min_index = i

    max_Area = max(h[min_index] * (e-s+1),

                   max(Area1(h, s, min_index-1),

                       Area1(h, min_index+1, e)))

    return max_Area

n = int(input())

a = list(map(int, input().split()))

print(Area1(a, 0, n-1))