python O(N) runtime O(1) space
Approach\nIterate with head right to left.\nAt any iteration maintain the following:\n- longest segment that ends exactly at head on the right side of the segme
# Approach\n$$Iterate$$ with $$head$$ right to left.\nAt any iteration maintain the following:\n- longest segment that ends exactly at $$head$$ on the right side of the segment: $$currLeft$$ stands for the number of prizes in this segment and $$leftEdge$$ stands for the left edge of the segment\n- longest segment that ends exactly at $$head$$ on the left side of the segment : $$currRight$$ stands for the number of prizes in this segment and $$rightEdge$$ stands for the right edge of the segment\n- number of prizes in the longest segment that ends at some indx larger or equal than $$head$$ on the left side of the segment: $$bestRight$$\n- best result until now: $$best$$\n\nat any iteration of $$head$$ we:\n - update $$currLeft$$ and $$leftEdge$$  by iterating left with $$leftEdge$$ as long as the segment is valid.\n - update $$currRight$$ and $$rightEdge$$  by iterating left with $$rightEdge$$ as long as the segment is not valid.\n - update $$bestRight$$ as max($$bestRight$$, $$currRight$$)\n - update $best$ as max($best$, $$currLeft$$ + $$bestRight$$)\n\nat the end return $best$.\ncorrectness follows straight forward from the algorithm description\nLets say for example that the best segments to pick are [10,30], [80,100] so by the time head got to 30 we already accounted for  [80,100]\nand now we have [10,30] in our hands, so we will account for this solution. (obviously we will never account a non existing solution so all good)\n\n\n# Complexity\n- Time complexity:\n$$O(N)$$\n$$leftEdge$$, $$rightEdge$$, $$head$$ always advance left and at each advnacment we do O(1) operations so all good.\n- Space complexity:\n$$O(1)$$: we simply hold 7 variables \n\n# Code\n```\nclass Solution(object):\n    def maximizeWin(self, prizePositions, k):\n        """\n        :type prizePositions: List[int]\n        :type k: int\n        :rtype: int\n        """\n        N = len(prizePositions)\n        head, left_edge, right_edge, curr_left, curr_right, best_right, best = N-1, N, N-1, 1, 0, 0, 0\n        \n        while head >= 0:\n            curr_left -= 1\n            while (left_edge > 0) and (prizePositions[head] - prizePositions[left_edge - 1] <= k):\n                left_edge -= 1\n                curr_left += 1\n            best = max(best, best_right + curr_left)\n            curr_right += 1\n            while prizePositions[right_edge] - prizePositions[head] > k:\n                curr_right -= 1\n                right_edge -= 1\n            best_right = max(best_right, curr_right)\n            head -= 1\n        return best\n\n\n\n        \n\n\n\n```
['Python']