Largest Rectangle

                            Solution in C :

In C ++ :




#include <stack>
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int N, h[100005];
int p = 1, s[100005];
int main() {
    scanf("%d", &N);
    for (int i = 1; i <= N; ++i) scanf("%d", &h[i]);
    int ans = 0;
    for (int i = 0; i < N + 2; ++i) {
        while (h[i] < h[s[p - 1]]) {
            int y = h[s[p - 1]];
            p--;
            ans = max(ans, (i - s[p - 1] - 1) * y);
        }
        s[p++] = i;
    }
    printf("%d\n", ans);
    return 0;
}








In Java :






import java.io.*;
import java.util.*;

public class Solution {
	static boolean[] valid;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		long[] ar = new long[n];


		for(int i=0; i<n; i++)
			ar[i] = sc.nextInt();
		
		int[] left = new int[n];
		int[] right = new int[n];
		Arrays.fill(left, -1); Arrays.fill(right, -1);

		Stack<Integer> st = new Stack<Integer>();

		for(int i=0; i<n; i++){
			while(st.size() > 0){
				if(ar[st.peek()] < ar[i]){
					left[i] = st.peek();
					break;
				}
				else
					st.pop();
			}
			st.push(i);
		}
		st.clear();
		for(int i=n-1; i>=0; i--){
			while(st.size() > 0){
				if(ar[st.peek()] < ar[i]){
					right[i] = st.peek();
					break;
				}
				else
					st.pop();
			}
			st.push(i);
		}
		// pArray(left);
		// pArray(right);
		long max = Integer.MIN_VALUE;
		for(int i=0; i<n; i++){
			long ans = 0;
			if(left[i] >= 0)
				ans+=ar[i]*(i - left[i] -1);
            else
                ans += ar[i] * i;
			if(right[i] > -1)
				ans+=ar[i]*(right[i] - i -1);
			else
				ans += ar[i] * (n - i-1);
			ans += ar[i];
			if(ans > max)
				max = ans;
			//System.out.println(ans);
		}
		System.out.println(max);
	}

	static void pArray(int[] ar){
		for(int i=0; i<ar.length; i++)
			System.out.print(ar[i] + " ");
		System.out.println();

	}
}








In  C :





#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
int main() {
    
    int i, j, k, n, h;
    int ar[100000];
    int area, max=0;
    
    scanf("%d",&n);
    for(i=0;i<=n;++i)
        scanf("%d",&ar[i]);
    
    for(i=0;i<=n;++i)
        {
        int c = 1;
        j = i-1;
        k = i+1;
        
        while(j>=0 && ar[j]>ar[i]){
            j--;
            c++;
        }
        while(k<=n && ar[k]>ar[i]){
            k++;
            c++;
        }
        
        
        area = c * ar[i];
        
        max = (area>max)? area : max;
       
    }
    
    printf("%d",max);
    return 0;
}








In  Python3 :






def solve(H) :
    s,i,m = [],0,0
    while i < len(H) :
        if not s or H[i] > H[s[-1]] :
            s.append(i)
            i += 1
        else :
            t = s.pop()
            a = H[t] * ((i - s[-1] -1)  if s else i)
            if a > m :
                m = a
                
    while s :
        t = s.pop()
        a = H[t] * ((i - s[-1] -1)  if s else i)
        if a > m :
            m = a
        
    return m           

N = int(input())
H = list(int(_) for _ in input().split())

print(solve(H))