Tutorialspoint.dev

Sliding Window Maximum (Maximum of all subarrays of size k)

Given an array and an integer k, find the maximum for each and every contiguous subarray of size k.

Examples :

Input :
arr[] = {1, 2, 3, 1, 4, 5, 2, 3, 6}
k = 3 
Output :
3 3 4 5 5 5 6

Input :
arr[] = {8, 5, 10, 7, 9, 4, 15, 12, 90, 13}
k = 4 
Output :
10 10 10 15 15 90 90


Method 1 (Simple)
Run two loops. In the outer loop, take all subarrays of size k. In the inner loop, get the maximum of the current subarray.

C/C++

#include <stdio.h>
  
void printKMax(int arr[], int n, int k)
{
    int j, max;
  
    for (int i = 0; i <= n - k; i++) {
        max = arr[i];
  
        for (j = 1; j < k; j++) {
            if (arr[i + j] > max)
                max = arr[i + j];
        }
        printf("%d ", max);
    }
}
  
int main()
{
    int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;
    printKMax(arr, n, k);
    return 0;
}

Java

// Java Program to find the maximum for each and every contiguous subarray of size k.
  
public class GFG {
    // Method to find the maximum for each and every contiguous subarray of size k.
    static void printKMax(int arr[], int n, int k)
    {
        int j, max;
  
        for (int i = 0; i <= n - k; i++) {
  
            max = arr[i];
  
            for (j = 1; j < k; j++) {
                if (arr[i + j] > max)
                    max = arr[i + j];
            }
            System.out.print(max + " ");
        }
    }
  
    // Driver method
    public static void main(String args[])
    {
        int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        int k = 3;
        printKMax(arr, arr.length, k);
    }
}
  
// This code is contributed by Sumit Ghosh

Python3

# Python program to find the maximum for 
# each and every contiguous subarray of
# size k
  
# Method to find the maximum for each
# and every contiguous subarray of s 
# of size k
def printMax(arr, n, k):
    max = 0
    
    for i in range(n - k + 1):
        max = arr[i]
        for j in range(1, k):
            if arr[i + j] > max:
                max = arr[i + j]
        print(str(max) + " ", end = "")
  
# Driver method
if __name__=="__main__":
    arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    n = len(arr)
    k = 3
    printMax(arr, n, k)
  
# This code is contributed by Shiv Shankar 

C#

// C# program to find the maximum for
// each and every contiguous subarray of
// size kusing System;
using System;
  
class GFG {
    // Method to find the maximum for
    // each and every contiguous subarray
    // of size k.
    static void printKMax(int[] arr, int n, int k)
    {
        int j, max;
  
        for (int i = 0; i <= n - k; i++) {
  
            max = arr[i];
  
            for (j = 1; j < k; j++) {
                if (arr[i + j] > max)
                    max = arr[i + j];
            }
            Console.Write(max + " ");
        }
    }
  
    // Driver method
    public static void Main()
    {
        int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        int k = 3;
        printKMax(arr, arr.Length, k);
    }
}
  
// This Code is Contributed by Sam007

PHP

<?php
// PHP program to find the maximum 
// for each and every contiguous 
// subarray of size k
  
function printKMax($arr, $n, $k)
{
    $j; $max;
  
    for ($i = 0; $i <= $n - $k; $i++)
    {
        $max = $arr[$i];
  
        for ($j = 1; $j < $k; $j++)
        {
            if ($arr[$i + $j] > $max)
            $max = $arr[$i + $j];
        }
        printf("%d ", $max);
    }
}
  
// Driver Code
$arr = array(1, 2, 3, 4, 5, 
             6, 7, 8, 9, 10);
$n = count($arr);
$k = 3;
printKMax($arr, $n, $k);
  
// This Code is Contributed by anuj_67.
?>

This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter