Last Updated: 30 Nov, 2021

3 Subarray

Hard

Asked in company

Solve now

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.

Print the starting indexes(0 based) of all the 3 intervals you are going to select to maximise the overall sweetness of your candies. If there are multiple answers, print the lexicographically smallest one.

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

Solve now

Approaches

01 Approach

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’

Solve now

02 Approach

Let’s create another array ‘W’ where ‘W[i]’ denotes the sum of all the elements from ‘i’ to ‘i’ + ‘K’ - 1.

We can do this by using prefix sums or managing the sum of the interval as a window slides along the array.

Now we need to find ‘i’, ‘j’, ‘l’ such that ‘i’ + ‘K’ <= ‘j’ , ‘j’ + ‘K’ <= ‘l’ and sum of ‘W[i]’ + ‘W[j]’ + ‘W[l]’ is maximum.

If we fix ‘j’, then we need to final the smallest ‘i’ from the range 0 to ‘j’ - ‘K’ and the smallest ‘l’ from the range ‘j’ + ‘K’ to ‘N’.

We can solve these problems with dynamic programming.

Let’s create an array ‘left’ where ‘left[i]’ denotes the smallest index of the best subarray we can select from 0 to ‘i’.

Similarly, we can create an array ‘right’ where ‘right[i]’ denotes the smallest index of the best subarray we can select from ‘i’ to ‘N’ - 1.

Thus, in the end for every ‘j’ we know the best ‘i’ is present in ‘left[j - K]’ and best ‘l’ is present in ‘right[j + K]’.

Algorithm:

Initialise an integer array ‘ans’ of size 3 to {-1, -1, -1}.
Initialise ‘mx’ to 0.
Initialise ‘currSum’ to 0.
Initialise an array ‘W’ of size ‘N’ - ‘K’ + 1 to 0.
Run a loop ‘i’ from 0 to ‘N’ - 1
- Add ‘A[i]’ to ‘currSum’
- If ‘i’ >= ‘K’
  - Subtract ‘A[i - K]’ from ‘curSum’
- If ‘i’ - ‘K’ + 1 >= 0
  - Update ‘W[i - K + 1]’ to ‘curSum’
Initialise an array ‘left’ of size ‘N’ to 0.
Initialise ‘best’ to 0.
Run a loop ‘i’ to size of ‘W’ - 1
- If ‘W[i]’ is greater than ‘W[best]’, update ‘best’ to ‘i’.
- Assign ‘best’ to ‘left[i]’

Initialise an array ‘right’ of size ‘N’ to 0.
Initialise ‘best’ to the size of ‘W’ - 1.
Run a loop ‘i’ from size of ‘W’ - 1 to 0
- If ‘W[i]’ >= ‘W[best]’, update ‘best’ to ‘i’.
- Assign ‘best’ to ‘right[i]’
Run a loop ‘j’ from ‘K’ to size of ‘W’ - ‘K’ - 1
- Initialise ‘i’ to ‘left[j - K]’ and ‘l’ to ‘right[j + K]’
- Initialise ‘curSum’ to ‘W[i]’ + ‘W[j]’ + ‘W[l]’
- If ‘ans[0]’ is equal to -1 or ‘curSum’ > ‘mx’
  - Update ‘ans’ to {i, j, l}.
Return ‘ans’.

Solve now