Largest Sum Subarray with at least K Numbers

Moderate
0/80
profile
Contributed by
8 upvotes
Asked in companies
FacebookIvy Comptech

Problem statement

Given an array 'arr' and a number 'k'.


Find the largest sum of the subarray containing at least 'k' numbers. It may be assumed that the size of the array is at least 'k'.


Example : 
Input: 'arr' = [1, 4, -2] and 'k' = 2

Output: 5

Explanation: The subarray with the largest sum is [1, 4]. So the sum will be 5.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains two space-separated integers, ‘n’ and ‘k’.

The second line contains ‘n’ space-separated integers, representing the array ‘arr’ elements.


Output Format : 
Print the largest sum of the subarray containing at least 'k' numbers.


Note : 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Sample Input 1 :
4 2
-3 -1 2 -2


Sample Output 1 :
1


Explanation For Sample Input 1 :
The subarray with the largest sum is [-1, 2]. So the sum will be 1.


Sample Input 2 :
3 2
1 4 -2


Sample Output 2 :
5


Explanation For Sample Output 2 :
The subarray with the largest sum is [1, 4]. So the sum will be 5.


Sample Input 3 :
4 4 
-14 12 11 -20


Sample Output 3 :
-11


Expected time complexity :
The expected time complexity is O('n').


Constraints :
1 <= 'n' <= 10 ^ 5
1 <= 'k' <= 'n'
-10 ^ 5 <= 'arr[i]' <= 10 ^ 5

Time Limit: 1 sec
Hint

Try to check all subarrays.

Approaches (3)
Brute Force

The basic idea is to check all the subarrays possible for the array. We find the sum of all subarrays having at least ‘k’ numbers and find the maximum sum from all of them.

Here is the algorithm :

  1. Create a variable (say, ‘res’) to store the largest sum and initialize it with a small value.
  2. Run a loop from 0 to ‘n’ - ‘k’ + 1 (say, iterator ‘i’).
    • Create a variable (say, ‘tempSum’) to store the sum of the subarray and initialize it with 0.
    • Run a loop from ‘i’ to ‘n’ (say, iterator ‘j’)
      • Update ‘tempSum’ by adding ‘arr[j]’ to it.
      • Check if ‘j’ - ‘i’ + 1 is greater than equal to ‘k’  (subarray consists of at least ‘k’ numbers).
        • Update ‘res’ by the maximum of ‘res’ and ‘tempSum’.
  3. Return ‘res’.
Time Complexity

O(n ^ 2), where ‘n’ is the size of the array.

We iterate the array once to iterate the elements and run another nested loop to find the subarrays. Therefore, the overall time complexity will be O(n ^ 2).

Space Complexity

O(1)

We don’t use any extra space. Therefore, the overall space complexity will be O(1).

Code Solution
(100% EXP penalty)
Largest Sum Subarray with at least K Numbers
Full screen
Console