Java O(n) slide window with dp
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \nAssume dp[j] is the max
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nAssume dp[j] is the max segment length from (0, i).\ndp[j] = max(dp[j - 1], valid(i, j)).\nFor (1,2,3,4) k = 4. If we add a new element 5.\n(1,2,3,4,5)\ndp[4] = range(0, 5) since (5 - 1 <= k) valid range(0, 4). \nIf the new added is value 6. \n(1,2,3,4,6) since 6 - 1 > 5, dp[4] = dp[3].\nFor all valid segment (i, j), max (dp[i - 1] + (j - i + 1)) will be the answer.\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    public int maximizeWin(int[] A, int k) {\n        //dp[i] means array from [0, i - 1] max segment length;\n        int n = A.length, res = 0;\n        int[] dp = new int[n];\n        for(int i = 0, j = 0; i < n; ++i){\n            while(j < n && A[j] - A[i] <= k){\n                int prev = j - 1 >= 0 ? dp[j - 1]: 0;\n                dp[j] = Math.max(prev, j - i + 1);\n                ++j;\n            }\n//            int prev = i - 1 >= 0 ? dp[i - 1] : 0;\n//            res = Math.max(prev + j - i, res);\n        }\n        for(int i = 0, j = 0; i < n; ++i){\n            while(j < n && A[j] - A[i] <= k){\n                ++j;\n            }\n            int prev = i - 1 >= 0 ? dp[i - 1] : 0;\n            res = Math.max(j - i + prev, res);\n        }\n        return res;\n    }\n}\n```
['Java']