The Widest Container

Difficulty: 1500 3000 ms 128 MB

two-pointers

Choose two walls; the water they hold is (distance) × (shorter wall's height). Print the maximum over all pairs.

Input: the first line has N (N ≥ 2); the second line has N non-negative heights.

Output: the maximum container capacity.

Constraints:

• 2 ≤ N ≤ 10⁵
• 0 ≤ h_i ≤ 10⁹

Sample Tests

9
1 8 6 2 5 4 8 3 7

49

2
1 1

1

Read the Editorial