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. 
?> 

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

C/C++

Java

Python3

C#

PHP

tags:

leave a comment

0 Comments

Subscribe to Our Newsletter

Top Followed books