Find the maximum possible area

Question

Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container.

One solution could be that we take each and every line and find area with every line. This takes O(n^2). Not time efficient.

Another solution could be using DP to find the maximum area for every index, and then at index n, we will get the maximum area. I think it's O(n).

Could there be more better solutions?

Answer 1

Many people here are mistaking this problem to maximal rectangle problem, which is not the case.

Solution

1. Delete all the elements aj such that ai >= aj =< ak and i > j < k. This can be done in linear time.
   1. Find the maximum value am
   2. Let as = a1
   3. For j = 2 through m-1, if as >= aj, delete aj, else as = aj
   4. Let as = an
   5. For j = n-1 through m+1, if as >= aj, delete aj, else as = aj
2. Notice that the resulting values look like a pyramid, that is, all the elements on the left of the maximum are strictly increasing and on the right are strictly decreasing.
3. i=1, j=n. m is location of max.
4. While i<=m and j>=m
   1. Find area between ai and aj and keep track of the max
   2. If ai < aj, i+=1, else j-=1

Complexity is linear (O(n))