Linear time using monotonic queue + sliding window
Intuition\nMight as well be greedy with placement of two intervals and make them disjoint. Why make them overlapping and risk missing out on some prizes?\n\n# A
# Intuition\nMight as well be greedy with placement of two intervals and make them disjoint. Why make them overlapping and risk missing out on some prizes?\n\n# Approach\nThought about binary search but realized we can solve it in linear time with a sliding window approach and monotonic queue. Straightforward sliding window approach yields the max number of prizes for any interval of size k starting at some index i in the input array.\n\nAs we iterate, we throw those results into a queue. This allows us to keep track of the best interval we\'ve already seen -- when a previously seen interval ends before our current interval begins, we update `best_single` to denote the best interval to the left that\'s disjoint from the current one. Because it\'s disjoint we don\'t need to worry about double counting prizes.\n\n# Complexity\n- Time complexity:\nO(n), the queue can never have more than n elements, and we iterate once over the input array.\n\n- Space complexity:\nO(n) due to queue\n\n# Code\n```\nclass Solution {\npublic:\n    int maximizeWin(vector<int>& ps, int k) {\n        const int n = ps.size();\n        auto right = 0;\n        auto best_single = 0;\n        queue<pair<int, int>> q;\n        auto best = 0;\n        for (auto left = 0; left < n; ++left) {\n            while (!q.empty() && q.front().first < ps[left]) {\n                const auto [r, count] = q.front();\n                q.pop();\n                best_single = max(best_single, count);\n            }\n            while (right < n && ps[right] - ps[left] <= k) ++right;\n            best = max(best, best_single + right - left);\n            q.emplace(ps[right - 1], right - left);\n        }\n        return best;\n    }\n};\n```
['C++']