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

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
75 upvotes
Asked in companies
MicrosoftExpedia GroupAdobe

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.

Detailed explanation ( Input/output format, Notes, Images )
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
Hint

Naively check every pair of non-overlapping subarrays.

Approaches (2)
Brute Force

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.
Time Complexity

O(N * N * K), where ‘N’ denotes the size of array/list ARR and ‘K’ denotes the given length of which subset needs to be found.

 

The inner loop variable ‘j’ varies with the outer loop variable ‘i’ as i + K. 

For i = 0, j varies from K to N - K. So, the loop runs N - 2 * K times.

For i = 1, j varies from K + 1 to N - K. So, the loop runs N - 2 * K - 1 times. 

For i = 2, j varies from K + 2 to N - K. So, the loop runs N - 2 * K - 2 times.(and so on)

For i = N - 2 * K, j varies from N - K to N - K. So, the loop runs 1 time.

 

So, the total number of times the function (getSum) is executed is:

1 + 2 + 3 + 4 + …. + (N - 2 * K - 2) + (N - 2 * K - 1) + (N - 2 * K) = (N - 2 * K)(N - 2 * K + 1)/2

 

The time complexity to find the sum of K elements using loop in getSum function is O(K).

So, the overall time complexity is O(N * N * K).

Space Complexity

O(1).

 

As constant space is used.

Code Solution
(100% EXP penalty)
Maximum sum of two non-overlapping subarrays of a given size
Full screen
Console