Intuitive python solution -- Beats 100%
Intuition\n Describe your first thoughts on how to solve this problem. \nwe need to:\n- calulate valid segment lengths\n- Find two (non-ovelapping) segments tha
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nwe need to:\n- calulate valid segment lengths\n- Find two (non-ovelapping) segments that maximizes the coverage. For each segment, we look back and see what is the longest segment before and add that to the current segment length as a potential answer.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n- Segmenmt length: use sliding window to calculate valid segment length. Note that using sliding window we also count overlapping segments, so we don\'t need to worry about them when doing the next step \n- Max of two (using memorization/DP): We charachtrize a segment by its $$left$$ and $$right$$ index. Once we idnetify a valid segment (by increasing r$$ight$$ pointer to a certain threshold), we can store the longest segment so far up to the index $$right$$. However, we are interested in longest segment ending before $$left$$ index, so we query the memory ($$max_so_far$$) at $$left$$ index (which is set before when we where identifing some earlier valid segment).\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(n)$$\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(n)$$\n\n# Code\n```python3 []\nfrom heapq import heappush, heappop\nfrom bisect import bisect_right\n\nclass Solution:\n    def maximizeWin(self, prizePositions: List[int], k: int) -> int:\n\n        # check if having two segment of length k is possible\n        if prizePositions[-1] - prizePositions[0] < 2*k:\n            return len(prizePositions)\n        \n        # store max segment length up to the index\n        max_so_far = [0] * (len(prizePositions)+1)\n        \n        left = right = 0\n        ans = 0\n        \n        # dynamic sliding window to calculate valid segments\n        for right in range(len(prizePositions)):\n            while prizePositions[right] - prizePositions[left] > k :\n                left += 1\n            \n            # a valid segment length\n            seg_len = right-left+1\n\n            # update max seg len up to the right+1 pointer\n            max_so_far[right+1] = max(max_so_far[right], seg_len)\n\n            # incorportate the longest segment before current segment\n            ans = max(seg_len + max_so_far[left], ans)\n\n        # handle ans with two overlapping segments        \n        return min(ans, len(prizePositions))\n        \n```
['Python3']