摘要
Title: 2555. 两个线段获得的最多奖品
Categories: 枚举右维护左、二分、前后缀分解、dp

2555. 两个线段获得的最多奖品

题意

在 X轴上有一些奖品。给你一个整数数组 prizePositions ，它按照非递减顺序排列，其中 prizePositions[i] 是第 i 件奖品的位置。数轴上一个位置可能会有多件奖品。再给你一个整数 k 。

你可以同时选择两个端点为整数的线段。每个线段的长度都必须是 k 。你可以获得位置在任一线段上的所有奖品（包括线段的两个端点）。注意，两个线段可能会有相交。

比方说 k = 2 ，你可以选择线段 [1, 3] 和 [2, 4] ，你可以获得满足 1 <= prizePositions[i] <= 3 或者 2 <= prizePositions[i] <= 4 的所有奖品 i 。
请你返回在选择两个最优线段的前提下，可以获得的最多奖品数目。

思路

枚举右维护左
看到两个线段（或者两个别的，类比两数之和）的问题，想到这个思路，对右边的线段进行枚举，然后维护左边的线段。题目要求覆盖尽可能多的礼物，那么两个线段不相交，尽可能多的覆盖是最优的
1. 枚举右线段的右端点，通过二分，求出最远可以到达的左端点
2. 左端点往左的区间，就是第一个线段存在的区间了，那么我们需要求出 [0, r] 中选出一个长度为k的线段，最多覆盖多少礼物，记为dp[r]
3. 这个dp值是可以边求边算的，当我们枚举第二个线段时，我们就知道了以这个右端点为端点的覆盖礼物数量，但是我们也可以不选这个右端点，那么dp值就是 max(dp[r - 1], r - l + 1)
4. 这样我们左侧的线段就不用枚举考虑，直接取dp值即可
前后缀分解
遇到分成两个区间的，想到前后缀分解，也就是选择一个分界点，分成前面和后面两部分，前面选一个线段，后面选一个线段即可
1. 和之前思路一样，不过这里求单个线段礼物最大数为：使用滑动窗口技术来计算这个数组，具体是遍历 prizePositions，维护一个窗口 [i, j]，确保 prizePositions[j] - prizePositions[i] 不超过 k，更新前缀最大值数组
2. 然后计算dp值，还是选与不选的问题
3. 前缀数组 prefix 记录了从左到右可以获得的最大奖品数（通过一个长度为 k 的线段），后缀数组 suffix 记录了从右到左可以获得的最大奖品数，后缀计算 (flag = -1)：当 flag = -1 时，表示我们在反向（从右到左）计算。
  在这种情况下，数组 prizePositions 被反转，窗口的长度也需要调整
4. 枚举分界点即可，前面dp加上后面dp取最大

代码

class Solution:
    def maximizeWin(self, prizePositions: List[int], k: int) -> int:
        n = len(prizePositions)
        dp = [0] * (n + 1)
        ans = 0
        for i in range(n):
            x = bisect.bisect_left(prizePositions, prizePositions[i] - k)
            ans = max(ans, i - x + 1 + dp[x])
            dp[i + 1] = max(dp[i], i - x + 1)
        return ans

class Solution:
    def maximizeWin(self, prizePositions: List[int], k: int) -> int:
        n = len(prizePositions)

        def calc(flag: int):
            prefix = Arr.array(0, n + 1)
            i = 0
            for j in range(n):
                while flag * (prizePositions[j] - prizePositions[i]) > k:
                    i += 1
                # 选与不选
                prefix[j + 1] = Math.max(prefix[j], j - i + 1)
            return prefix

        prefix = calc(1)
        prizePositions = prizePositions[::-1]
        suffix = calc(-1)

        ans = 0
        for i in range(n + 1):
            ans = Math.max(ans, prefix[i] + suffix[n - i])
        return ans