Hello, here i have a question which is a variation of the famous ‘Largest Rectangle Under Histogram’ problem:

Problem Statement:

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.

eg: input:

9

1 8 6 2 5 4 8 3 7

output:

49

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?