Python Sliding Window O(N). Clean Code + Intuition + Similar problem
Intuition\nThis is the same problem as:\nhttps://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/editorial, Approach 1: Bidirectional Dynamic Programm
# Intuition\nThis is the same problem as:\nhttps://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/editorial, Approach 1: Bidirectional Dynamic Programming, where you want a max to the left of i and a max to the right of i.\n\n# Approach\n1. Use a counter to get a num -> count mapping so the distance to iterate becomes less\n2. Make an array in_span_l which is the maximum possible score making a span to the left of this index. Use a sliding window to compute this, tracking all numbers within k span of the index. \n3. Similarly, make an array in_span_r is the maximum possible to the right of this index. \n4. The max is max(in_span_l[i] + in_span_r[i + 1]) for any i        \n```\n1 2 3 5 7    num\n2 2 2 1 2    count of num\n2 4 6 6 6    in_span_l\n6 4 3 3 2    in_span_r\n```\n\n# Code\n```\n\nclass Solution:\n    def maximizeWin(self, prizePositions: List[int], k: int) -> int:\n\n        counts = Counter(prizePositions)\n        counts_arr = [(num, count) for num, count in counts.items()]\n        if len(counts_arr) == 1:\n            return counts_arr[0][1]\n        num_ind = list(counts.keys())\n        in_span = []\n        rolling_count = 0\n        j = 0\n        pre = -inf\n        for i in range(len(counts_arr)):\n            rolling_count += counts_arr[i][1]\n            while num_ind[i] - num_ind[j] > k:\n                rolling_count -= counts_arr[j][1]\n                j += 1\n            in_span.append(max(rolling_count, pre))\n            pre = max(rolling_count, pre)\n\n        in_span_r = []\n        rolling_count = 0\n        j = len(counts_arr) - 1\n        pre = -inf\n        for i in range(len(counts_arr) - 1, -1, -1):\n            rolling_count += counts_arr[i][1]\n            while num_ind[j] - num_ind[i] > k:\n                rolling_count -= counts_arr[j][1]\n                j -= 1\n            in_span_r.append(max(rolling_count, pre))\n            pre = max(rolling_count, pre)\n        in_span_r = list(reversed(in_span_r))\n        # print(list(range(len(counts_arr))), \'i\')\n        # print(list(counts.keys()), \'num\')\n        # print(list(counts.values()), \'count of num\')\n        # print(in_span, \'span_l\')\n        # print(in_span_r, \'span_r\')\n        max_all = -inf\n        for i in range(len(in_span) - 1):\n            max_all = max(max_all, in_span[i] + in_span_r[i + 1])\n        return max_all\n```
['Python3']