ECOMP - Editorial

Contest

Author: Dhruv Purwar

Tester: Rahul Sharma

Editorialist: Rahul Sharma

DIFFICULTY:

Easy

PREREQUISITES:

Sliding window, loops

PROBLEM:

Given array of size N find continuous K elements in it such that their sum is maximum.

QUICK EXPLANATION:

Make use of sliding window and update maximum answer till end of array.

EXPLANATION:

Subtask #1:
Run two loops outer loop for starting index and inner to loop K elements and calculate sum and update answer within outer loop. TIme complexity is O(N*K).
It is a brute force and will only pass this subtask.

Subtask #2:
Optimized solution is to use sliding window. Run initial loop from 1 to K and store the sum and mark as current max. Now run another loop from K+1 till N and update the sum for a window by subtracting last element of previous window and adding last element of current window from the previous sum. If the sum is greater than current max then update the current max. Finally return current max as answer when loop ends. This will pass all testcases.

COMPLEXITIES:

Time Complexity: O(N) for each test file.
Auxillary Space: O(1) for each test file.

SOLUTIONS:

Setter's Solution (CPP)
#include <bits/stdc++.h>
using namespace std;


int maxSum(int arr[], int n, int k)
{
	
	int max_sum = 0;
	for (int i = 0; i < k; i++)
		max_sum += arr[i];

	
	int window_sum = max_sum;
	for (int i = k; i < n; i++) {
		window_sum += arr[i] - arr[i - k];
		max_sum = max(max_sum, window_sum);
	}

	return max_sum;
}


int main()
{
	
	int n,k,x;
        cin>> n>>k;
        int arr[n];
        for(int i=0;i<n;i++){
           cin>>x;
           arr[i]=x;         
        }
	cout << maxSum(arr, n, k);
	return 0;
}
Setter's Solution (Python)
def maxSum(arr, n, k):

	
	if (n < k):
           return -1
	
	
	res = 0
	for i in range(k):
		res = res+arr[i]

	
	curr_sum = res
	for i in range(k, n):
	
		curr_sum += arr[i] - arr[i-k]
		res = max(res, curr_sum)

	return res

def Convert(string):
    list1 = []
    list1[:0] = string
    return list1
# Driver code
arr=[]
n,k = [int(X) for X in input().split()]

arr=list(map(int,input().strip().split()))[:n]

print(maxSum(arr, n, k))
1 Like