# 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 ```