Hello, here i have a question which is a variation of the famous ‘Largest Rectangle Under Histogram’ problem:
We are given a 1-indexed array of N positive integers,
For each i in [1,N] element Ai,
Consider every integer j in range [0,Ai],
Points(i,j) are plotted on an x-y graph.
Find maximum area of rectangle that can be formed by selecting any 4 points and whose sides are parallel to x and y axis.
1 8 6 2 5 4 8 3 7
I have tried a lot but can only think of a simple brute force method, where i consider every pair of points(i1,Ai1) and (i2,Ai2), so the breadth is i2-i1 and height is min(Ai1,Ai2).
But this method has upper bound complexity of O(N^2) which is not allowed.
How at all can we approach this to solve in max O(N) time?