Pick Two Trees for a Zipline That Maximizes Height Times Span

Trees stand in a straight row, one unit apart: tree i is at position i and has height heights[i]. You will install one zipline between two different trees. The cable is attached at the same height on both trees, so it can be mounted no higher than the shorter of the two. Rate a zipline between trees i and j (with i < j) by min(heights[i], heights[j]) * (j - i): the mounting height times the horizontal span. Return the highest rating any zipline can get.

Function Signature

def best_zipline(heights: list[int]) -> int:

Rules

• A zipline joins two distinct trees. Trees standing between them do not block the cable and do not affect the rating.
• Return only the maximum rating, which is a single integer.

Constraints

• 2 <= len(heights) <= 10^5
• 1 <= heights[i] <= 10^4
• The rating is at most 10^4 * (10^5 - 1), which is below 10^9 and fits in a 32-bit signed integer.

Examples

Example 1

Input: heights = [3, 1, 4, 2, 5]
Output: 12

Trees 0 and 4 give min(3, 5) * (4 - 0) = 12. Trees 2 and 4 give only min(4, 5) * 2 = 8.

Example 2

Input: heights = [2, 7, 1, 7, 1, 3]
Output: 14

Trees 1 and 3 give min(7, 7) * 2 = 14, which beats the widest pair, trees 0 and 5 (2 * 5 = 10), and trees 1 and 5 (3 * 4 = 12).

Example 3

Input: heights = [6, 9]
Output: 6

The only zipline joins trees 0 and 1: min(6, 9) * 1 = 6.