A telecom crew has planted a row of n relay towers along a mountain ridge, numbered 0 to n-1 by position, each with its own antenna height. Any two towers can be linked to form a signal corridor: the corridor's width is the horizontal distance between the two towers' positions, and the corridor's usable height is capped by the shorter of the two antennas (a signal cannot rise above the lower antenna without leaking out of the corridor). The crew wants to choose two towers that maximize the corridor's coverage area, defined as width times the usable height.
Given the heights of all n towers, find the maximum possible coverage area achievable by linking any two distinct towers.
Line 1: a single integer n, the number of towers.
Line 2: n space-separated non-negative integers, the antenna height of each tower in order of position.
A single integer: the maximum coverage area over all pairs of distinct towers.
2 <= n <= 1000000 <= height[i] <= 10000 for every towerExample 1
Input
5 3 9 4 7 2
Expected
14
Explanation
Checking all pairs, the best is towers at positions 1 and 3 with heights 9 and 7: width = 3-1 = 2, usable height = min(9,7) = 7, giving area 2*7 = 14, which beats every other pairing (e.g. positions 0 and 3 give 3*min(3,7)=9).
Example 2
Input
2 5 5
Expected
5
Explanation
With only two towers, they must be linked: width = 1, usable height = min(5,5) = 5, so the area is 1*5 = 5.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →