Maximum sum of two non-overlapping subarrays of a given size

Posted: 25 Oct, 2020
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

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.
Approach 1

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.
Try Problem