Medium

Maximize Win From Two Segments

LAB

Given sorted prize positions and segment length k, return the maximum prizes covered by two segments.

EXAMPLES

Example 1

Input
{
  "prizePositions": [
    1,
    1,
    2,
    2,
    3,
    3,
    5
  ],
  "k": 2
}

Output
7

FUNCTION SHAPE

prizePositions: intArrayk: int→int

SOLUTION NOTE

Sliding window + prefix max. For each right endpoint, combine with best segment ending before left.

Reveal reference solution +

pythonREFERENCE

def maximizeWin(self, prizePositions: List[int], k: int) -> int:
    n = len(prizePositions)
    # best[i] = max prizes from one segment ending at or before position i
    best = [0] * (n + 1)

    res = 0
    left = 0
    for right in range(n):
        while prizePositions[right] - prizePositions[left] > k:
            left += 1
        count = right - left + 1
        best[right + 1] = max(best[right], count)
        res = max(res, count + best[left])

    return res

TimeO(n)

SpaceO(n)

Open on LeetCode ↗