Siding window is a method for iterating over a linear collection by maintaining a window range indices (a group of consecutive elements) to satisfy the problem constraints

Sliding window is an improvement over brute force iteration to reduce the time complexity

## Problem

• Given an array A and a number k

• Write an algorithm to find the maximum sum of k consecutive elements in A

## Example

• Input: [5, 7, 2, 9, 4] and 2

• Expected output: 13

• Explanation: 9 and 4 are 2 consecutive elements have maximum sum

## Approach 1: Brute force

• Iterating over `a` one by one element to find max sum
``````public class SubarrayMaxSumBruteforce {
public static int maxSumBruteforce(int[] A, int k) {
int maxSum = Integer.MIN_VALUE;

for (int i = 0; i < A.length - k + 1; i++) {
int currentSum = 0;

for (int j = 0; j < k; j++) {
currentSum += A[i+j];
}

if (currentSum > maxSum) maxSum = currentSum;
}

return maxSum;
}

public static void main(String[] args) {
System.out.println(maxSumBruteforce(new int[]{5, 7, 2, 9, 4}, 2));
}
}
``````
• Output
``````13
``````
• Time complexity: O(n*k)

• Space complexity: O(1)

## Approach 2: Sliding window

• Iterating over `a` window by window to find max sum
``````public class SubarrayMaxSumWindowSliding {
public static int maxSumWindowSliding(int[] A, int k) {
int windowsSum = 0, maxSum = Integer.MIN_VALUE;

for (int i = 0; i < k; i++) {
windowsSum += A[i];
}

for (int i = k; i < A.length; i++) {
windowsSum += A[i] - A[i-k];
if (windowsSum > maxSum) maxSum = windowsSum;
}

return maxSum;
}

public static void main(String[] args) {
System.out.println(maxSumWindowSliding(new int[]{-5, -7, -2, -9, -4}, 2));
}
}
``````
• Output
``````-9
``````
• Time complexity: O(n)

• Space complexity: O(1)