Last Updated: 25 Nov, 2021
Largest Sum Subarray with at least K Numbers
Moderate
Asked in companies
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.
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.
Approaches
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 :
- Create a variable (say, ‘res’) to store the largest sum and initialize it with a small value.
- 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’.
- Return ‘res’.
The basic idea is to store the sum of the previous window to save space. We find the sum first window. For subsequent windows, we add the current element of the array and update the maximum sum. We then check whether the first element of the previous window is negative or not. If negative, we remove that element from the sum and again update the result.
Here is the algorithm :
- Create a variable (say, ‘tempSum’) to store the sum and initialize it with 0.
- Run a loop from 0 to ‘k’ (say, iterator ‘i’) to find the sum of the first window.
- Add ‘arr[i]’ to the ‘tempSum’.
- Create a variable (say, ‘prevSum’) to store the sum of previous numbers and initialize it with 0.
- Create a variable (say, ‘idx’) to store the index of elements of the previous window.
- Create a variable (say, ‘res’) to store the largest sum and initialize it with ‘tempSum’.
- Run a loop from ‘k’ to ‘n’ (say, iterator ‘i’) to find the next window.
- Add ‘arr[i]’ to ‘tempSum’ to add the current element.
- Add ‘arr[idx]’ to ‘prevSum’ to add the last element.
- Increment ‘idx’ by 1.
- Update ‘res’ by the maximum of ‘res’ and ‘tempSum’.
- Check ‘prevSum’ is less than 0.
- Decrease ‘tempSum’ by ‘prevSum’.
- Update ‘res’ by the maximum of ‘res’ and ‘tempSum’.
- Update ‘prevSum’ to 0.
- Return ‘res’.
The basic idea is to find the maximum sum for every index of the array. We then use the concept of the sliding window technique of size ‘k’. We first find the sum of the first ‘k’ elements of the array. For finding the sum of the next window, we first remove the first element of the previous window and add the current element. We now check whether the current sum is maximum or not. We also add the max sum of the last window in the current window to check if the sum is maximized or not.
Here is the algorithm :
- Create a variable (say, ‘vec’) of the size of ‘n’ to store the maximum sum for every index and initialize the first index with ‘arr[0]’.
- Create a variable (say, ‘tempSum’) to store the sum and initialize with ‘arr[0]’.
- Run a loop from 1 to ‘n’ (say, iterator ‘i’) to update the maximum sum for every index.
- Update ‘tempSum’ with the maximum of ‘arr[i]’ and ‘tempSum’ + ‘arr[i]’.
- Update ‘vec[i]’ with ‘tempSum’.
- Reinitialize ‘tempSum’ with 0.
- Run a loop from 0 to ‘k’ (say, iterator ‘i’) to find the sum of the first window.
- Add ‘arr[i]’ to ‘tempSum’.
- Create a variable (say, ‘res’) to store the largest sum, initialize it with a small value, and initialize it with ‘tempSum’.
- Run a loop from ‘k’ to ‘n’ (say, iterator ‘i’) to find the sum of the next windows.
- Add ‘arr[i]’ to ‘tempSum’ and subtract ‘arr[i - k]’ from it.
- Update ‘res’ by the maximum of ‘res’ and ‘tempSum’.
- Again update ‘res’ by the maximum of ‘res’ and sum of ‘tempSum’ and ‘vec[i - k]’.
- Return ‘res’.