CR3 - Editorial

Practice

Author: Jaymeet Mehta

Tester: Vatsal Parmar

Editorialist: Mann Mehta

DIFFICULTY

Cakewalk

PREREQUISITES

Array Manipulations

PROBLEM

Given an array A of length N your task is to find the maximum sum of k length contiguous subarray possible.

EXPLANATION

Here we will using Sliding Window Technique.

Let consider an array a1,a2,a3. . . an

Here K will be our window size, we just iterate towards the array sliding the windows of size k total (n-k+1) times.

let see how it works:


a1,a2,a3,a4,a5,a6,a7,a8,a9,a10 and K=4
initailly window element contains : {a1,a2,a3,a4} hence sum=a1+a2+a3+a4.

Now we iterate such that new element added in the window and first element remove from the window.


Adding a5 element {a1,a2,a3,a4,a5} hence window size has changed.

Removing a1 element {a2,a3,a4,a5} hence we get back our window size is 4. and it’s sum = sum+a5-a1.

we iterate till end then among all the sum we consider max out of this.

TIME COMPLEXITY

Time Complexity is O(N) per test case.

SOLUTIONS

Editorialist Solution