DP: leftMax + rightMax
Intuition\nFor every index i, if we can get leftMax[i-1] and rightMax[i], we can iterate through i and get the max result.\n\nleftMax[i]: max on the left of ind
# Intuition\nFor every index ```i```, if we can get ```leftMax[i-1]``` and ```rightMax[i]```, we can iterate through ```i``` and get the max result.\n\n```leftMax[i]```: max on the left of index ```i``` (including ```i```) \n```rightMax[i]```: max on the right of index ```i``` (including ```i```)\n\nTo get ```leftMax[i]```: the max between ```leftMax[i-1]```, and the number in the window of size ```k``` from ```i``` to the left, i.e., ```i - j + 1```, where ```j``` is the most left element meeting the window size ```k``` requirement for ```i```.\n\nTo get ```rightMax[i]```: the max between ```rightMax[i+1]```, and the number in the window of size ```k``` from ```i``` to the right, i.e., ```j - i + 1```, where ```j``` is the most right element meeting the window size ```k``` requirement for ```i```.\n\nTime complexity: ```O(n)```\n- ```O(n)``` to get ```leftMax```\n- ```O(n)``` to get ```rightMax```\n- ```O(n)``` to get result\n\n# Code\n```\nclass Solution {\n    public int maximizeWin(int[] prizePositions, int k) {\n        int n = prizePositions.length;\n        int[] leftMax = new int[n], rightMax = new int[n];\n        // leftMax[i]: max on the left of i (including i) \n        // rightMax[i]: max on the right of i (including i)\n\n        int j = 0;\n        leftMax[0] = 1;\n        for(int i = 1; i < n; i++) {\n            while (prizePositions[i] - prizePositions[j] > k) j++;\n            leftMax[i] = Math.max(leftMax[i - 1], i - j + 1);\n            // leftMax[i]: the max between leftMax[i-1], and\n            // the number in the window of size k from i to the left\n        }\n        \n        j = n - 1;\n        rightMax[n - 1] = 1;\n        for(int i = n - 2; i >= 0; i--) {\n            while (prizePositions[j] - prizePositions[i] > k) j--;\n            rightMax[i] = Math.max(rightMax[i + 1], j - i + 1);\n            // rightMax[i]: the max between rightMax[i+1], and\n            // the number in the window of size k from i to the right\n        }\n        \n        int result = 0;\n        \n        for(int i = 0; i <= n; i++) {\n            // XXXXXXXXXX i-1 i XXXXXXXXXXX for each i to get leftMax[i - 1] + rightMax[i]\n            // edge cases: when i = 0 no leftMax, when i = n - 1 no rightMax\n            result = Math.max(result, (i == 0 ? 0 : leftMax[i - 1]) + (i == n ? 0 : rightMax[i]));\n        }\n        \n        return result;\n    }\n}\n```
['Java']