Maximize Win From Two Segments

Maximize Win From Two Segments

What is this problem about?

In this problem, you are given an array of prize positions on a number line, sorted in ascending order. You are allowed to place two segments (lines), each of length k, anywhere on the number line. Your goal is to maximize the total number of prizes captured by these two segments. The segments can overlap, but a prize is only counted once.

Why is this asked in interviews?

This is a sophisticated combination of the Sliding Window and Dynamic Programming patterns. It tests a candidate's ability to optimize two independent choices. Interviewers use it to see if you can break the problem into: "What is the best single segment ending here?" and "How can I combine that with the best single segment after here?" to guarantee $O(N)$ linear time complexity.

Algorithmic pattern used

This problem leverages Dynamic Programming with a Sliding Window.

1. Iterate a right pointer through the array.
2. Maintain a left pointer such that positions[right] - positions[left] <= k. This sliding window represents a single valid segment ending at right. The number of prizes in this segment is right - left + 1.
3. Maintain an array dp where dp[i] stores the maximum prizes a single segment can capture entirely within the prefix positions[0...i-1].
4. As you calculate the window ending at right, the maximum total prizes using two segments is the current window size plus the best non-overlapping segment to its left, which is precisely dp[left]. Update your global maximum.

Example explanation

Positions: [1, 2, 3, 5, 8], k = 2. DP array tracks max single segment size. Max_Total = 0.

• right = 0 (1): left = 0. Window size = 1. dp[1] = max(dp[0], 1) = 1. Total = size + dp[left] = $1 + 0 = 1$.
• right = 1 (2): left = 0 (Diff $2-1 \le 2$). Size = 2. dp[2] = 2. Total = $2 + dp[0] = 2$.
• right = 2 (3): left = 0 (Diff $3-1 \le 2$). Size = 3. dp[3] = 3. Total = $3 + dp[0] = 3$.
• right = 3 (5): left = 2 (Diff $5-3 \le 2$, moved left from 0). Size = 2 (prizes at 3, 5). dp[4] = max(dp[3], 2) = 3. Total = size + dp[left] = $2 + dp[2]$. Since dp[2] is 2 (from segment [1, 2]), total = $2 + 2 = 4$. Max prizes captured by two segments is 4.

Common mistakes candidates make

A common mistake is trying to evaluate overlapping segments. The optimal configuration of two segments will never need to overlap. If they overlap, you could just merge them into one larger segment or slide one away to potentially catch more prizes without losing any. By strictly querying dp[left], you mathematically enforce that the second segment is completely distinct from the current window.

Interview preparation tip

When tackling problems involving "Two optimal subarrays/segments", the standard playbook is to use an array to cache the "best single answer so far" from left to right. Then, as your sliding window evaluates the second choice, it simply looks up the cached answer that sits just outside its left boundary. This converts an $O(N^2)$ pair-checking algorithm into an elegant $O(N)$ single pass.