Last Updated: 25 Oct, 2020
Maximum sum of two non-overlapping subarrays of a given size
Moderate
Asked in companies
You are given an array/list ARR of integers and a positive integer ‘K’. Your task is to find two non-overlapping subarrays (contiguous) each of length ‘K’ such that the total sum of these subarrays is maximum.
For Example:
If you are given ARR = [2, 5, 1, 2, 7, 3, 0] and K = 2, the output is 17.
We can choose non-overlapping subarrays [2, 5] and [7, 3] to get a total sum of 17 (i.e. 2 + 5 + 7 + 3) which is the maximum possible sum.
You can assume that the array will always contain at least two non-overlapping subarrays with size ‘K’. So, the answer will always exist.
Input Format:
The first line of input contains an integer 'T' representing the number of test cases or queries to be processed. Then the test case follows.
The first line of each test case contains two single space-separated integers ‘N’ and ‘K’, respectively. ‘N’ represents the size of the array/list.
The second line of each test case contains N single space-separated integers representing the array/list elements.
Output Format :
For each test case, print a single line containing a single integer representing the total maximum possible sum.
The output of each test case will be printed in a separate line.
Note:
You do not need to print anything, it has already been taken care of. Just implement the function.
Constraints:
1 <= T <= 10 ^ 2
2 <= N <= 5 * 10 ^ 3
1 <= K <= N / 2
-10 ^ 5 <= ARR[i] <= 10 ^ 5
Where ‘N’ is the number of elements in the array/list ARR.
ARR[i] represents the ith element of ARR.
Time Limit: 1 sec.
Approaches
The problem boils down to finding the sum of all pairs of non-overlapping subarrays of size K. We can naively find all non-overlapping subarray pairs by two nested loops, with the outer loop (loop variable i) running from 0 to N - 2 * K and inner loop (loop variable j) running from i + K to N - K. The range of loops is taken in such a way that it will prevent any overlapping of subarrays.
Following is the algorithm for this approach:
- We initialize MAXSUM to -1000000000.
- We run a loop (loop variable i) from 0 to N - 2 * K.
- We find the sum of a subarray of size K starting from index i (i.e. GETSUM(ARR, i, i+K)). Let this sum be sum1.
- Now, we again run a loop (loop variable j) from i + K to N - K.
- We find the sum of another subarray of size K starting from index j (i.e. GETSUM(ARR, j, j+K)). Let this sum be sum2.
- If MAXSUM is less than the total sum (sum1 + sum2), we update it i.e MAXSUM = sum1 + sum2.
- Finally, we return MAXSUM as the answer.
We store the prefix sum (the sum of all elements from first until the last element) in the PREFIXSUM array to calculate the sum of subarrays of size K easily.
We maintain a DP array where DP[i] denotes the subarray sum that is maximum among all possible subarrays of size K till index i.
For the subarray of size K ending at index i (i.e. [i - K + 1: i]), we need to find the maximum subarray sum of size K that ends before this subarray (i.e. ending on or before i - K) which is given by DP[i - K].
Here is the complete algorithm:
- We initialize MAXSUM to -1000000000.
- We create a PREFIXSUM array.
- We create DP array as follows:
- Initialize DP[K] to sum of the first subarray of size K i.e. PREFIXSUM[K].
- We run a loop from K + 1 to N.
- We set DP[i] to the maximum of DP[i - 1] and PREFIXSUM[i] - PREFIXSUM[i - K].
- We run a loop from 2 * K to N. The beginning of this loop is chosen as such to prevent any overlap between the two subarrays.
- If the total of the subarray sum from indices [i - K + 1, i] and DP[i - K] (i.e. maximum subarray sum ending on or before index i - K) is more than MAXSUM, then update it.
- Finally, we return MAXSUM as the answer.
Similar problems