23

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

Difficulty: MEDIUM
Contributed By
Deepanshu Dhingra
Avg. time to solve
15 min
Success Rate
85%

Problem Statement

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.
Sample Input 1 :
1
5 2
7 1 6 9 2
Sample Output 1 :
23

Sample Output 1 Explanation:

For the first test case, all subarrays of size 2 and their sums are:
{7, 1} : sum = 7+1 = 8
{1, 6} : sum = 1+6 = 7
{6, 9} : sum = 6+9 = 15
{9, 2} : sum = 9+2 = 11

The two non-overlapping subarrays with the maximum total sum are {7,1} and {6,9}. So, the output is the total of their sums i.e. 15 + 8 = 23.
Sample Input 2 :
2
10 3
10 1 3 15 30 40 4 50 2 1
9 2
4 8 -1 -23 8 7 -6 5 0
Sample Output 2 :
142
27
Reset Code
Full screen
copy-code
Console