ArrayTwo PointersGreedy
Each number is the height of a vertical line drawn at that index. Pick two lines that, together with the x-axis, hold the most water. Print that maximum amount (width times the shorter height).
Input
Line 1: n. Line 2: n heights.
Output
Print the maximum area of water a container can store.
Constraints
2 <= n <= 10^5 0 <= height <= 10^4
Example 1
Input
9 1 8 6 2 5 4 8 3 7
Output
49
Lines of height 8 and 7 are 7 apart: 7 * 7 = 49.