LC9-11

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

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

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

• 比方说 k = 2 ，你可以选择线段 [1, 3] 和 [2, 4] ，你可以获得满足 1 <= prizePositions[i] <= 3 或者 2 <= prizePositions[i] <= 4 的所有奖品 i 。

请你返回在选择两个最优线段的前提下，可以获得的 最多 奖品数目。

示例 1：

输入：prizePositions = [1,1,2,2,3,3,5], k = 2
输出：7
解释：这个例子中，你可以选择线段 [1, 3] 和 [3, 5] ，获得 7 个奖品。

示例 2：

输入：prizePositions = [1,2,3,4], k = 0
输出：2
解释：这个例子中，一个选择是选择线段 [3, 3] 和 [4, 4] ，获得 2 个奖品。

提示：

• 1 <= prizePositions.length <= 105
• 1 <= prizePositions[i] <= 109
• 0 <= k <= 109
• prizePositions 有序非递减。

滑动窗口+动态规划

假设要求一段线段的最大覆盖，很容易想到求出以每个下标f[i]为结尾的最大覆盖，使用的方法可以是二分或者滑动窗口。
如果考虑两端线段的最大覆盖的话，不妨设g[i]表示以0到i的下标结尾的最大覆盖的最大值。那么则有：
$g[i]=max(g[i−1],f[i])$
当遍历到一个下标的时候，可以得到以当前下标为末尾的最长覆盖和这个下标之前的所有下标的最长覆盖的最大值，可以贪心，最优解一定位于其中的某个值：
$ans=max(ans,f[i]+g[i−f[i]])$

class Solution {
    public int maximizeWin(int[] prizePositions, int k) {
        int n = prizePositions.length;
        int[] f = new int[n], g = new int[n];
        int ans = 0;
        for (int l = 0, r = 0; r < n; r++) {
            while (prizePositions[r] - prizePositions[l] > k) {
                l++;
            }
            f[r] = r - l + 1;
            if (r == 0) {
                g[r] = f[r];
            } else {
                g[r] = Math.max(g[r - 1], f[r]);
            }
            if (r - f[r] >= 0) {
                ans = Math.max(ans, f[r] + g[r - f[r]]);
            }
        }
        ans = Math.max(ans, g[n - 1]);
        return ans;
    }
}