O(N) approach using dynamic programming and sliding window
Approach\nDynamic Programming with Sliding Window\n\n# Complexity\n- Time complexity: O(n)\n\n- Space complexity: O(n)\n\n# Code\n\nclass Solution(object):\n   
# Approach\nDynamic Programming with Sliding Window\n\n# Complexity\n- Time complexity: $$O(n)$$\n\n- Space complexity: $$O(n)$$\n\n# Code\n```\nclass Solution(object):\n    def maximizeWin(self, P, k):\n        #Have a dp array to record the max length of the first segment at i:\n        dp = [0] * len(P)\n        res = 0\n        left = 0 # first pointer of the sliding window\n        for right in range(len(P)):\n            while P[right] - P[left] > k:\n                # sliding window, contract left if (P[left],P[right]) is not a valid segment\n                left += 1\n\n            # now, (left, right) is valid\n            # calculate this segment length starts from left to right\n            this_segment = right - left + 1\n\n            # first max segment length is the dp[left-1] because this segment starts from left\n            first_segment = dp[left-1]\n\n            # result is the max of current res or (first_segment + second segment(this_segment))\n            res = max(res, first_segment + this_segment)\n\n            # dp[right] is the max of dp[right-1] or this_segment\n            dp[right] = max(dp[right-1], this_segment)\n\n        return res\n```
['Python']