Given, an array
arr[]
of size
n
having non-negative integers
h1, h2, ..., hn
, where each represents a point at coordinate
(i, hi)
. There are
n
vertical lines drawn such that the two endpoints of line
i
are at
(i, hi)
and
(i, 0)
. Write a program to find two lines, which together with the x-axis forms a container, such that the container contains the most water.
Problem Note:
You may not slant the container and
n
is at least 2.
The above vertical lines are represented by array [1, 2, 4, 3]. In this case, the maximum area of water (the section between horizontal line) the container can contain is 4.
Example:
Input: arr[] = [1, 2, 4, 3]
Output: 4
Explanation: The area of water between the lines of height 2 and 3 is maximum and equal to 2*2 = 4.