---
# System prepended metadata

title: 2555. Maximize Win From Two Segments
tags: [Leetcode, Dynamic Programming, Sliding Window, Medium]

---

# 2555. Maximize Win From Two Segments
###### tags: `Leetcode` `Medium` `Sliding Window` `Dynamic Programming`
Link: https://leetcode.com/problems/maximize-win-from-two-segments/description/
## 思路
思路[参考](https://leetcode.com/problems/maximize-win-from-two-segments/solutions/3141449/java-c-python-dp-sliding-segment-o-n/)
```dp[i]```表示在```prizePositions[0:i]``` maximum number of prizes of **one** segment
sliding window从左到右扫描 window里面是一个valid segment 假设扫到```prizePositions[i]``` 那么以```prizePositions[i]```结尾的valid segment的起点我们设为```j```
这个sliding window的number of prizes是```i-j+1```
在前```j```个elements里面 我们可以cover最多```dp[j]```个elements 所以我们总共可以用两个segment cover ```i-j+1+dp[j]```个element
## Code
```python=
class Solution:
    def maximizeWin(self, prizePositions: List[int], k: int) -> int:
        left, right = 0, 0
        dp = [0]*(len(prizePositions)+1)
        ans = 0
        for right in range(len(prizePositions)):
            while left<right and prizePositions[right]-prizePositions[left]>k:
                left += 1
            dp[right+1] = max(dp[right], right-left+1)
            ans = max(ans, right-left+1+dp[left])
        return ans
```