Show problems as
Classic problem #1537HardArrayTwo PointersDynamic ProgrammingGreedy

Get the Maximum Score

Real-world version: Best Total Across Two Ridges
Tracked in this browser only
Read Get the Maximum Score on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Two ridges each carry a line of cairns. west lists the altitudes of the cairns on the west ridge in the order they are met, and east does the same for the east ridge. Both lists are strictly increasing, so no ridge repeats an altitude, though an altitude may appear on both ridges.

A walker begins at the first cairn of either ridge and works upwards. From the cairn they are standing on they step to the next cairn of the ridge they are on. If the cairn they are standing on has an altitude that also appears on the other ridge, they may instead cross over and step to the cairn that follows that shared altitude on the other ridge. The walk ends when the walker steps past the last cairn of the ridge they are on.

The score of a walk is the sum of the altitudes of the cairns it stands on, each counted once. Return the highest score any walk can reach.

Examples

Example 1

Input
west = [3, 7, 12, 20], east = [7, 9, 12, 30]
Output
61

One walk starts on the west ridge at 3 and 7, crosses at altitude 7, carries on over 9 and 12 on the east ridge and finishes there at 30. It stands on 3, 7, 9, 12 and 30, which total 61.

Example 2

Input
west = [2, 5, 11], east = [4, 6]
Output
18

No altitude appears on both ridges, so no crossing is ever available and a walk covers one whole ridge. The west ridge totals 18 and the east ridge totals 10.

Example 3

Input
west = [8], east = [8]
Output
8

Each ridge carries a single cairn at altitude 8, and a shared cairn counts once, so any walk scores 8.

Constraints

  • 1 <= west.length, east.length <= 10^5
  • 1 <= west[i], east[i] <= 10^7
  • west and east are strictly increasing.
  • The highest score is at most 10^13.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def best_ridge_total(west: list[int], east: list[int]) -> int:
Java
public long bestRidgeTotal(int[] west, int[] east)

More on the same topics