Maximum sum two non-overlapping subarrays of given size
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

Question

Maximum sum two non-overlapping subarrays of given size

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.

Accepted Answer

Can be done by first calculating the max sum and then the min sum and calculating the difference at each position.

Accepted Answer

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.

Space Complexity: O(1)Explanation:

O(1).

As constant space is used.

Time Complexity: OtherExplanation:

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).

Accepted Answer

Dynamic Programming

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:
1. Initialize DP[K] to sum of the first subarray of size K i.e. PREFIXSUM[K].
2. We run a loop from K + 1 to N.
  1. 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.
1. 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.

Space Complexity: O(n)Explanation:

O(N), where ‘N’ denotes the size of the array.

Arrays of size (N + 1) will be used to store the prefix sum and maximum subarray sum calculated so far. So, the overall space complexity is O(N).

Time Complexity: O(n)Explanation:

O(N), where ‘N’ denotes the size of the array.

The time complexity to create a prefix sum array is O(N).

The time complexity to create a DP array is O(N).

The time complexity of looping from 2 * K to N is O(N). So, the overall time complexity is O(N).