# Maximize Win From Two Segments
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximize-win-from-two-segments)
Canonical: https://scaleengineer.com/dsa/problems/maximize-win-from-two-segments
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array
---
## Problem
There are some prizes on the **X-axis**. You are given an integer array `prizePositions` that is **sorted in non-decreasing order**, where `prizePositions[i]` is the position of the `ith` prize. There could be different prizes at the same position on the line. You are also given an integer `k`.

You are allowed to select two segments with integer endpoints. The length of each segment must be `k`. You will collect all prizes whose position falls within at least one of the two selected segments (including the endpoints of the segments). The two selected segments may intersect.

* For example if `k = 2`, you can choose segments `[1, 3]` and `[2, 4]`, and you will win any prize i that satisfies `1 <= prizePositions[i] <= 3` or `2 <= prizePositions[i] <= 4`.

Return _the **maximum** number of prizes you can win if you choose the two segments optimally_.

**Example 1:**

**Input:** prizePositions = [1,1,2,2,3,3,5], k = 2
**Output:** 7
**Explanation:** In this example, you can win all 7 prizes by selecting two segments [1, 3] and [3, 5].

**Example 2:**

**Input:** prizePositions = [1,2,3,4], k = 0
**Output:** 2
**Explanation:** For this example, **one choice** for the segments is `[3, 3]` and `[4, 4],` and you will be able to get `2` prizes. 

**Constraints:**

* `1 <= prizePositions.length <= 105`
* `1 <= prizePositions[i] <= 109`
* `0 <= k <= 109 `
* `prizePositions` is sorted in non-decreasing order.

# Approaches
## Brute Force
A straightforward but inefficient approach is to try every possible pair of segments. Since the optimal segments will have their endpoints aligned with prize positions to maximize coverage, we can assume each segment starts at some `prizePositions[i]`. We can iterate through all pairs of starting indices `(i, j)` for the two segments. For each pair, we calculate the total number of unique prizes covered by the union of the two segments and keep track of the maximum number found.
**Time:** O(N^3), where N is the number of prizes. The three nested loops iterate through all pairs of starting positions and then all prizes. · **Space:** O(N) in this implementation due to the HashSet. It can be O(1) if we calculate counts without a set.
**Pros:** Simple to understand and implement.
**Cons:** The time complexity is very high, making it unsuitable for the given constraints.
### Explanation
This method exhaustively checks every combination of two segments. The start of each segment is chosen from one of the prize positions. For each pair of segments, we determine the total number of unique prizes they cover. 

To implement this, we can use nested loops. The outer loop selects the starting prize for the first segment, and the inner loop selects the starting prize for the second segment. For each pair of segments, we can iterate through all the prizes and count how many fall within at least one of the two segments. To handle overlaps correctly (i.e., not counting a prize twice if it's in both segments), we can use a `HashSet` to store the indices of the prizes collected.

```java
import java.util.HashSet;

class Solution {
    public int maximizeWin(int[] prizePositions, int k) {
        int n = prizePositions.length;
        if (n == 0) {
            return 0;
        }
        int maxPrizes = 0;

        // If only one segment is used
        if (n > 0) {
            for (int i = 0; i < n; i++) {
                int rightBound = prizePositions[i] + k;
                int count = 0;
                for (int p = i; p < n; p++) {
                    if (prizePositions[p] <= rightBound) {
                        count++;
                    } else {
                        break;
                    }
                }
                maxPrizes = Math.max(maxPrizes, count);
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                long start1 = prizePositions[i];
                long end1 = start1 + k;
                long start2 = prizePositions[j];
                long end2 = start2 + k;

                HashSet<Integer> collectedPrizes = new HashSet<>();
                for (int p = 0; p < n; p++) {
                    if ((prizePositions[p] >= start1 && prizePositions[p] <= end1) || 
                        (prizePositions[p] >= start2 && prizePositions[p] <= end2)) {
                        collectedPrizes.add(p);
                    }
                }
                maxPrizes = Math.max(maxPrizes, collectedPrizes.size());
            }
        }
        return maxPrizes;
    }
}
```
This version has a time complexity of O(N^3). A slightly better O(N^2 log N) approach would involve calculating the counts for each segment and their intersection using binary search instead of the innermost loop, but it's still too slow for the given constraints.
### Algorithm
1. Initialize `maxPrizes` to 0.
2. Iterate through each possible starting position `i` for the first segment, from `0` to `n-1`.
3. Inside this loop, iterate through each possible starting position `j` for the second segment, from `i` to `n-1`.
4. For each pair `(i, j)`, define the two segments:
   - `S1 = [prizePositions[i], prizePositions[i] + k]`
   - `S2 = [prizePositions[j], prizePositions[j] + k]`
5. Count the number of prizes in the union of `S1` and `S2`. A simple way to do this is to iterate through all prizes from `p = 0` to `n-1` and check if `prizePositions[p]` falls into `S1` or `S2`. A `HashSet` can be used to store the indices of the prizes collected to avoid double counting.
6. Update `maxPrizes` with the maximum count found.
7. Return `maxPrizes`.

## Dynamic Programming with Split Point
A much more efficient approach uses dynamic programming. The core idea is to split the `prizePositions` array into two parts and find the best single segment in each part. By trying all possible split points, we can find the global optimum.

Let `dp_left[i]` be the maximum number of prizes we can win with one segment using only the first `i` prizes (i.e., `prizePositions[0...i-1]`).
Let `dp_right[i]` be the maximum number of prizes we can win with one segment using prizes from index `i` to the end (i.e., `prizePositions[i...n-1]`).

Both `dp_left` and `dp_right` arrays can be computed in O(N) time using a two-pointer technique. Once we have these arrays, we can iterate through all possible split points `i` (from `0` to `n`). For each split point, we consider taking the best segment from the left part `[0...i-1]` and the best segment from the right part `[i...n-1]`. The total prizes would be `dp_left[i] + dp_right[i]`. The maximum of these sums over all `i` will be our answer. This works because any pair of non-overlapping segments will be separated by some split point `i`, and even overlapping segments can be shown to be covered by this logic.
**Time:** O(N), where N is the number of prizes. Each step (computing `dp_left`, `dp_right`, and combining them) takes linear time. · **Space:** O(N) for the two DP arrays, `dp_left` and `dp_right`.
**Pros:** Highly efficient with linear time complexity.; Guaranteed to find the optimal solution.
**Cons:** Requires extra space for the DP arrays.
### Explanation
The algorithm proceeds in three main steps:
1.  **Compute `dp_left`:** We iterate from `i = 1` to `n`. We use a sliding window approach with two pointers, `l` and `i-1`, to find the maximum number of prizes in a segment ending at or before `i-1`. The left pointer `l` is advanced to maintain the window constraint `prizePositions[i-1] - prizePositions[l] <= k`. `dp_left[i]` is the maximum of `dp_left[i-1]` and the current window size.
2.  **Compute `dp_right`:** Similarly, we iterate from `i = n-1` down to `0`. We use a sliding window with pointers `i` and `r` to find the maximum prizes in a segment starting at or after `i`. The right pointer `r` is advanced to satisfy `prizePositions[r] - prizePositions[i] <= k`. `dp_right[i]` is the maximum of `dp_right[i+1]` and the current window size.
3.  **Combine results:** We iterate through all possible split points `i` from `0` to `n`. The maximum prizes are found by `max(maxPrizes, dp_left[i] + dp_right[i])`.

```java
class Solution {
    public int maximizeWin(int[] prizePositions, int k) {
        int n = prizePositions.length;
        if (n == 0) {
            return 0;
        }

        // dp_left[i] = max prizes in a single segment within prizePositions[0...i-1]
        int[] dp_left = new int[n + 1];
        int l = 0;
        for (int i = 1; i <= n; i++) {
            while (prizePositions[i - 1] - prizePositions[l] > k) {
                l++;
            }
            dp_left[i] = Math.max(dp_left[i - 1], (i - 1) - l + 1);
        }

        // dp_right[i] = max prizes in a single segment within prizePositions[i...n-1]
        int[] dp_right = new int[n + 1];
        int r = n - 1;
        for (int i = n - 1; i >= 0; i--) {
            while (prizePositions[r] - prizePositions[i] > k) {
                r--;
            }
            dp_right[i] = Math.max(dp_right[i + 1], r - i + 1);
        }

        int maxPrizes = 0;
        for (int i = 0; i <= n; i++) {
            maxPrizes = Math.max(maxPrizes, dp_left[i] + dp_right[i]);
        }

        return maxPrizes;
    }
}
```
### Algorithm
1. Create an array `dp_left` of size `n + 1`. `dp_left[i]` will store the maximum number of prizes obtainable from a single segment that is entirely contained within the subarray `prizePositions[0...i-1]`.
2. Populate `dp_left` from left to right. Use a two-pointer `l` to find the start of the longest valid segment ending at `i-1`. `dp_left[i] = max(dp_left[i-1], length_of_segment_ending_at_i-1)`.
3. Create an array `dp_right` of size `n + 1`. `dp_right[i]` will store the maximum prizes from a single segment entirely within `prizePositions[i...n-1]`.
4. Populate `dp_right` from right to left. Use a two-pointer `r` to find the start of the longest valid segment starting at `i`. `dp_right[i] = max(dp_right[i+1], length_of_segment_starting_at_i)`.
5. The problem is now to find a split point `i` that maximizes the sum of prizes from a segment on the left and a segment on the right. Initialize `maxPrizes = 0`.
6. Iterate `i` from `0` to `n`, and for each `i`, calculate `dp_left[i] + dp_right[i]`. Update `maxPrizes` with the maximum sum found.
7. The final answer is `maxPrizes`.

# Solutions
### Java

```java
class Solution {
public
  int maximizeWin(int[] prizePositions, int k) {
    int n = prizePositions.length;
    int[] f = new int[n + 1];
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
      int x = prizePositions[i - 1];
      int j = search(prizePositions, x - k);
      ans = Math.max(ans, f[j] + i - j);
      f[i] = Math.max(f[i - 1], i - j);
    }
    return ans;
  }
private
  int search(int[] nums, int x) {
    int left = 0, right = nums.length;
    while (left < right) {
      int mid = (left + right) >> 1;
      if (nums[mid] >= x) {
        right = mid;
      } else {
        left = mid + 1;
      }
    }
    return left;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maximizeWin(vector<int> &prizePositions, int k) {
    int n = prizePositions.size();
    vector<int> f(n + 1);
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
      int x = prizePositions[i - 1];
      int j = lower_bound(prizePositions.begin(), prizePositions.end(), x - k) -
              prizePositions.begin();
      ans = max(ans, f[j] + i - j);
      f[i] = max(f[i - 1], i - j);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def maximizeWin(self, prizePositions: List[int], k: int) -> int: n = len(prizePositions) f = [0] * (n + 1) ans = 0 for i, x in enumerate(prizePositions, 1): j = bisect_left(prizePositions, x - k) ans = max(ans, f[j] + i - j) f[i] = max(f[i - 1], i - j) return ans

```