Sliding Window Algorithm

Problem: Given an array of integers of size?‘n’,?Our aim is to calculate the maximum sum of?‘k’?consecutive elements in the array.

Naive approach:

• Run 2 for loops one over the entire array and the other nested loop will run over the window and perform the necessary calculation

As we can see, over here the time - complexity will be of the order of O(k*n), where k is the window size and n is the length of the array.

Sliding Window Approach:

Brief: Sliding Window Algorithm?is a technique for reducing the complexity of algorithms. It is used such that the need for reusing the loops gets reduced and hence the program gets optimized. In this technique, we reuse the result of the previous step to compute the result of the next step.

Prerequisite: The use of Sliding Window technique can be done in a very specific scenario, where the?size of window?for computation is?fixed?throughout the complete nested loop. Only then the time complexity can be reduced.?

Data: Consider an array?arr[]?= {5, 2, -1, 0, 3} and value of?k?= 3 and?n?= 5

Implementation:

1. We compute the sum of first k elements out of n terms using a linear loop and store the sum in variable window_sum.
2. Then we will graze linearly over the array till it reaches the end and simultaneously keep track of maximum sum.
3. To get the current sum of block of k elements just subtract the first element from the previous block and add the last element of the current block.

Illustration:

Time Complexity: O(n)

Code:

def maxSum(arr, k):

????# length of the array

????n = len(arr)

??

????# n must be greater than k

????if n < k:

????????print("Invalid")

????????return -1

??

????# Compute sum of first window of size k

????window_sum = sum(arr[:k])

??

????# first sum available

????max_sum = window_sum

??

????# Compute the sums of remaining windows by

????# removing first element of previous

????# window and adding last element of

????# the current window.

????for i in range(n - k):

????????window_sum = window_sum - arr[i] + arr[i + k]

????????max_sum = max(window_sum, max_sum)

??

????return max_sum        

Links to my previous posts on the similar topic:

https://lnkd.in/gKENt5Pd

https://lnkd.in/gwm34WTj

https://lnkd.in/gz2J4y_2

https://lnkd.in/gDJ4_yxc