3 Subarray

Hard
0/120
Average time to solve is 50m
profile
Contributed by
4 upvotes
Asked in company
Facebook

Problem statement

There were ‘N’ candies placed one after another, ith of which has a sweetness value of ‘A[i]’.

In one operation, you can take exactly ‘K’ continuous candies, and once any candy is taken, it can not be used again. Once any segment is removed, that segment remains empty.

For example, If initially the array was [2, 1, 5, 6, 7] and you take candies from index 1 to 2. The array becomes [2, _ , _ , 6, 7]. Note that after removing the candies in the middle, the candies present in left and right do not join and thus can not be called continuous segments.

You are allowed to do 3 such operations, and you want to maximise the total sweetness value of all the candies you have.

Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains an integer ‘T’, denoting the number of test cases.

The first line of each test case contains two spaced integers ‘N’ and ‘K’, denoting the number of candies and the integer ‘K’.

The following line contains an array ‘A’ of ‘N’ spaced integers denoting the sweetness value of each candy.
Output Format: 
For each test case, print three single-spaced integers in a new line denoting the starting indexes(0 based) of all the 3 intervals.
Note: 
You are not required to print the expected output. It has already been taken care of. Just implement the function.
Constraints: 
1 <= T <= 10
1 <= N <= 2 * 10^4
1 <= A[i] <= 2^16
1 <= K <= floor(N / 3) 

Time Limit: 1 sec
Sample Input 1:
2
7 2
1 2 7 6 2 5 1
3 1
8 9 1
Sample Output 1:
0 2 4
0 1 2
Explanation for Sample Input 1:
In the first test case, you can select subarrays with indexes [0, 1], [2, 3] and [4, 5] to have the maximum sum. 
In the second test case, you can only select [0], [1] and [2].
Sample Input 2:
2
8 2
1 2 6 7 2 6 5 1
3 1
2 2 2
Sample Output 2:
1 3 5 
0 1 2
Hint

Can we check all possible ways?

Approaches (2)
Brute Force

Basically, we need to find three non-overlapping subarrays such that the sum of these three subarrays is maximum. We can use three nested loops to try to find all possible ways to select non-overlapping subarrays. 

To find the sum of the subarray quickly we will use the prefix sum.



 

Algorithm: 

  • Declare an integer array ‘ans’ of size 3
  • Initialise ‘mx’ to 0.
  • Create a prefix sum array with the name ‘pre’ of size ‘N’.
  • Run a loop ‘i’ from 0 to ‘N’ - 1
    • Run a loop ‘j’ from ‘i’ + ‘K’ to ‘N’ - 1
      • Run a loop ‘l’ from ‘l’ + ‘K’ to ‘N’ - 1
        • Let ‘sum’ be the sum of subarrays from the range ‘i’ to ‘i’ + ‘K’ - 1 , ‘j’ to ‘j’ + ‘K’ - 1 and ‘l’ to ‘l’ + ‘K’ - 1.
        • If ‘sum’ is greater than ‘mx’
          • Update ‘ans’ to {i, j, l} and ‘mx’ to the ‘sum’
  • Return ‘ans’
Time Complexity

O(N ^ 3), where ‘N’ is the size of the array.


 

We are using three nested loops to generate all possible ways to select three subarrays, so the final time complexity becomes O(N ^ 3).


 

Space Complexity

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


 

We are using another array to store the prefix sum, so the final space complexity is O(N).


 

Code Solution
(100% EXP penalty)
3 Subarray
Full screen
Console