-
Notifications
You must be signed in to change notification settings - Fork 0
/
WindowSliding.java
43 lines (40 loc) · 1.13 KB
/
WindowSliding.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
package code.datastructures.arrays;
public class WindowSliding {
/**
* This is the window sliding algorithm. This technique is useful to compute a running average,
* sum or finding adjacent pair.
* Level - Medium.
*/
public int slidingWindow(int[] arr, int windowSize) {
int maxSum = 0, windowSum = 0;
for (int i = 0; i < windowSize; i++) {
maxSum += arr[i];
}
windowSum = maxSum;
for (int i = windowSize; i < arr.length; i++) {
windowSum += arr[i] - arr[i - windowSize];
maxSum = Math.max(windowSum, maxSum);
}
return maxSum;
}
/**
* Given an array of size n, find the maximum for sum for k consecutive elements. Time complexity
* is O(n) and space complexity is O(1).
* Level - Medium.
*/
public int getMaximumSum(int[] arr, int k) {
if (k > arr.length) {
return -1;
}
int maxSum = 0, windowSum = 0;
for (int i = 0; i < k; i++) {
windowSum += arr[i];
}
maxSum = windowSum;
for (int i = k; i < arr.length; i++) {
windowSum += arr[i] - arr[i - k];
maxSum = Math.max(maxSum, windowSum);
}
return maxSum;
}
}