Given n vertical lines of the given heights on the x-axis, pick two so that the container they form (with the x-axis) holds the most water. The area between lines at positions i and j is min(height[i], height[j]) × (j − i).
Line 1: an integer n.
Line 2: n non-negative integers, the heights.
The maximum area.
Example 1
9 1 8 6 2 5 4 8 3 7
49
Lines at index 1 and 8: min(8,7)·7 = 49.
Example 2
2 1 1
1
min(1,1)·1 = 1.
Example 3
3 4 3 2
4
Best is index 0 and 2: min(4,2)·2 = 4.
Start with the widest pair — one pointer at each end.
The shorter line limits the area, so move the pointer at the shorter line inward; moving the taller one could never help.
Two pointers from both ends. Track the best area; always advance the pointer at the shorter line, since width only shrinks and only a taller line can improve the area.
import sys
d = list(map(int, sys.stdin.read().split()))
n = d[0]
h = d[1:1 + n]
lo, hi, best = 0, n - 1, 0
while lo < hi:
area = min(h[lo], h[hi]) * (hi - lo)
if area > best:
best = area
if h[lo] < h[hi]:
lo += 1
else:
hi -= 1
print(best)
Tell us what needs to change, who it affects and any important deadline. We will review the context and reply with useful next questions.