[Python] O(N*LogN) DP with binary search
Eg, k = 2\n\nSuppose we decide to pick current index, lets say item 1. Then we can pick all in range of 1 to 3 inclusive. So we simply binary search to find ind
Eg, k = 2\n\nSuppose we decide to pick current index, lets say item 1. Then we can pick all in range of 1 to 3 inclusive. So we simply binary search to find index that is strictly greater than 3 in `prizePositions`. This allows to remove the need to keep track of chosen values and reduce time complexity.\n\nWe can also choose not to pick any value at this point as well.\n\n```\nclass Solution:\n    def maximizeWin(self, prizePositions: List[int], k: int) -> int:\n        def binary(arr, find):\n            start = 0\n            end = len(arr)-1\n            res = len(arr)\n            while start <= end:\n                middle = (start+end)//2\n                if arr[middle] > find:\n                    res = min(res, middle)\n                    end = middle-1\n                else:\n                    start = middle+1\n            return res\n        \n        @cache\n        def dfs(k1, count):\n            if k1 >= len(prizePositions) or count == 2:\n                return 0\n            \n            y1 = -float(\'inf\')\n            y1 = max(y1, dfs(k1+1, count))\n            \n            nxtInd = binary(prizePositions, prizePositions[k1] + k)\n            y1 = max(y1, dfs(nxtInd, count+1) + nxtInd-k1)\n            \n            return y1\n        return dfs(0, 0)\n                    \n```
['Dynamic Programming', 'Memoization', 'Binary Tree', 'Python']