title
在 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 <= 1051 <= prizePositions[i] <= 1090 <= k <= 109prizePositions有序非递减。
solution
class Solution:
def maximizeWin(self, prizePositions: List[int], k: int) -> int:
n = len(prizePositions)
ans = 0
left = 0
pre = [0] * n
'''
求最大的两个区间。每个区间可以双指针计算。找到一个后，只要找到左边里的最大一个就可以，可以持久化记录。
'''
for i in range(n):
while left <= i and prizePositions[i] - prizePositions[left] > k:
left += 1
pre[i] = i - left + 1
ans = max(ans, pre[i] + (pre[left - 1] if left - 1 >= 0 else 0))
if i > 0:
pre[i] = max(pre[i], pre[i - 1])
# print(pre)
return ans