# Java O(n) time without Deque, A cool technique using Dynamic Programming.

• I have implemented a solution for the technique shown in this link. Look for the solution 2 given by Shashank Jain. Thanks!

http://stackoverflow.com/questions/8031939/finding-maximum-for-every-window-of-size-k-in-an-array

``````public class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if(nums == null || nums.length == 0) {
return new int[]{};
}

int length = nums.length;
int[] leftMax = new int[length];
int[] rightMax = new int[length];

leftMax[0] = nums[0];
rightMax[length - 1] = nums[length - 1];

for(int i = 1; i < length; ++i) {
leftMax[i] = (i % k == 0) ? nums[i] : Math.max(leftMax[i-1], nums[i]);
rightMax[length - 1 - i] = ((length - 1 - i) % k == 0) ? nums[length - 1 - i] :
Math.max(rightMax[length - i],nums[length - 1 - i]);
}

int[] res = new int[length - k + 1];

for(int i = 0; i < length - k + 1; ++i) {
res[i] = Math.max(leftMax[i + k - 1], rightMax[i]);
}
return res;
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.