HelloKoding

Practical coding guides

Sliding Window Maximum

In this article, you will learn to analyze and resolve the Sliding Window Maximum problem by using sliding window algorithm

Siding window is an algorithm 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

Approach 1: Brute force

  • Iterating over a one by one element to find max sum

SubarrayMaxSumBruteforce.java

package com.hellokoding.algorithm;

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

SubarrayMaxSumWindowSliding.java

package com.hellokoding.algorithm;

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)
Follow HelloKoding