Easy Solution
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem asks us to choose two intervals of length k from a sorted list of prize pos
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem asks us to choose two intervals of length k from a sorted list of prize positions to maximize the number of prizes we can collect. These intervals can overlap, but we want to find the optimal combination.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nSliding Window for One Interval:\n\nFor each position i, use a sliding window to find the maximum number of prizes that can be collected from an interval ending at position i and having a length of k.\nSimilarly, for each position i, find the maximum number of prizes that can be collected from an interval starting at position i using another sliding window.\nDynamic Programming Arrays:\n\nleftMax[i]: Maximum number of prizes from any interval ending at position i.\nrightMax[i]: Maximum number of prizes from any interval starting at position i.\nCombine the Two Intervals:\n\nFor each possible split between the two intervals, combine the best result from the first interval (leftMax[i-1]) and the best result from the second interval (rightMax[i]).\nMaximize the total number of prizes from these two intervals.\n\n# Complexity\n- Time complexity:\nThe sliding window approach runs in O(n), and combining the intervals also takes O(n), so the total time complexity is O(n).\n\n# Code\n```java []\nclass Solution {\n    public int maximizeWin(int[] prizePositions, int k) {\n        \n        int n = prizePositions.length;\n        int leftMax[] = new int[n];\n        int rightMax[] = new int[n];\n\n        leftMax[0] = 1;\n        for(int i = 1, j = 0; i < n; i++) {\n            while(prizePositions[i] - prizePositions[j] > k) {\n                j++;\n            }\n            leftMax[i] = Math.max(leftMax[i-1], i-j+1);\n        }\n\n        rightMax[n-1] = 1;\n        for(int i = n-2, j = n-1; i >= 0; i--) {\n            while(prizePositions[j] - prizePositions[i] > k) {\n                j--;\n            }\n            rightMax[i] = Math.max(rightMax[i+1], j-i+1);\n        }\n        \n        int res = 0 ;\n        for(int i = 0; i <= n; i++) {\n            res = Math.max(res, (i == 0 ? 0 : leftMax[i - 1]) + (i == n ? 0 : rightMax[i]));\n        }\n        return res;\n    }\n}\n```
['Java']