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))