- 這一題的關鍵在於追縱離開 window 時的數字,可以滿足的最大值,所以可以用 dp + sliding window 來解這一題。
class Solution {
public:
int maximizeWin(vector<int>& nums, int k) {
int n = nums.size(), left = 0, right = 0, res = 0;
unordered_map<int,int> dp;
int missed = 0;
while (right < n) {
while (right + 1 < n && nums[right] == nums[right+1]) right++;
if (nums[right] - nums[left] > k) {
while (nums[right] - nums[left] > k) {
missed = max(missed, dp[nums[left++]]);
}
}
dp[nums[right]] = right - left + 1;
right++;
res = max(res, right - left + missed);
}
return res;
}
};