Largest Rectangle in Histogram

Problem Statement

Largest Rectangle in Histogram Problem Description A histogram is drawn as a row of n vertical bars standing side by side on a common base line. Every bar is exactly 1 unit wide, and the i -th bar is heights[i] units tall. A bar of height 0 is an empty slot: it still takes up one unit of width, but nothing is drawn there. An axis-parallel rectangle is drawn inside the histogram. Its bottom edge lies on the base line, it covers one or more consecutive bars completely, and its height cannot exceed the height of any bar it covers. So a rectangle that covers bars l to r can be at most min(heights[l..r]) units tall, and its area is that height multiplied by its width r - l + 1 . Find the largest area such a rectangle can have. Complete the function solve(heights) , which receives the array of bar heights and returns the largest rectangle area. Input Format Read from standard input. n [heights[0],heights[1],...,heights[n-1]] Line 1 contains the integer n , the number of bars. Line 2 contains