Last Updated: 17 Dec, 2021
N-dates with Lili
Moderate
Cole is going on a date with Lili. But this date is a little strange, and it will last for ‘N’ days (day 1, day 2… day ‘N’) continuously. They will be going to the place known as ‘Kausani’. There are (‘N’ + ‘K’ - 1) restaurants (1, 2, …, ’N’ + ‘K’ - 1) situated on a line in ‘Kausani’.
On the ‘i-th’ day, they can go to any one of the restaurants from ‘i’ to ‘i’ + ‘K’ - 1, which Lilli will decide(one restaurant can be visited any number of times). You are given an array ‘A’ in which the ‘j-th‘ number denotes the number of coins that will be spent on restaurant ‘j’.
Cole is worried and wants to know the maximum total number of coins required on these N-dates with Lilli. Find the maximum total number of coins needed.
Examples:
‘N’ = 2
‘K’ = 2
‘A’ = {2, 3, 1}
On the 1st date, they can go to restaurant 1 or restaurant 2.
On the 2nd date, they can go to restaurant 2 or restaurant 3.
The possible combination of restaurants:
‘1’ and ‘2’ on 1st date and 2nd date respectively = 2 + 3 = 5
‘1’ and ‘3’ on 1st date and 2nd date respectively = 2 + 1 = 3
‘2’ and ‘2’ on 1st date and 2nd date respectively = 3 + 3 = 6
‘2’ and ‘3’ on 1st date and 2nd date respectively = 3 + 1 = 4
Maximum Total number of coins = max(5, 3, 6, 4) = 6
Input Format :
The first line contains an integer ‘T’ which denotes the number of test cases to be run. Then the test cases follow.
The first line of each test case contains two integers, ‘N’ and ‘K’, denoting the number of dates and the number of restaurants they can go to on each date, respectively.
The second line contains (‘N’ + ‘K’ - 1) space-separated integers, where the ‘I-th’ integer denotes the number of coins to be spent in the ‘I-th’ restaurant.
Output Format :
Print a single integer representing the maximum total number of coins required for each test case.
Print the output of each test case in a new line.
Note :
You don’t need to print anything. It has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 10
1 <= K <= N <= 10^5
1 <= ARR[i] <= 10^4
Sum of ‘N’ over all test cases is <= 10^5.
Time Limit: 1 sec
Approaches
Approach :
To calculate the maximum total number of coins for all the ‘N’ dates, we should calculate the maximum possible coins for each date and sum them up.
Algorithm :
- Initialise a variable ‘maxSum’ as 0.
- Loop through the dates from ‘I’ = 1 to ‘I’ = ‘N’:
- Initialise a variable ‘maxCoins’ as 0
- ‘maxCoins’ = max(‘A[i]’, ‘A[i + 1]’, … , ‘A[i + K - 1]’)
- ‘maxSum’ = ‘maxSum’ + ‘maxCoins’
- Return ‘maxSum’
Approach :
- The main difficulty is to find the maximum number of coins for each date.
- If we can tell till which restaurant, the ‘i-th’ restaurant has the maximum coins to be spent on. Then we can solve this problem.
For Example :
‘N’ = 4, ‘K’ = 3, ‘A’ = {3, 4, 2, 1, 9, 1}
restaurant number 1, has maximum coins up to restaurant number 1.
restaurant number 2, has maximum coins up to restaurant number 4.
restaurant number 5, has maximum coins up to restaurant number 6.
Now, on the first date, the restaurant with the maximum coins is restaurant 2.
Restaurant number 2 will also remain the restaurant with maximum coins on the second date.
Then restaurant 5 will be the restaurant with maximum coins.
- We will use a stack for calculating this for every restaurant.
- Now, we have to find the restaurant ‘j’’ which has maximum coins to be spent on among all available restaurants on a date, i.e., ‘A[j]’ = max{‘A[i]’, ‘A[i + 1]’, …, ‘A[i + K - 1]’}, then we will sum them up.
Algorithm :
- Initialise a variable ‘maxSum’ as 0.
- Initialise an array ‘maxUpto’ of length (‘N’ + ‘K’ - 1) with value 0.
- Initialise a stack ‘maxStack’ as an empty stack.
- Loop through the restaurants from ‘i’ = 1 to ‘i’ = ‘N’ + ‘K’ - 1 :
- while ‘maxStack’ is not empty and ‘A[i]’ > ‘A[maxStack.top]’
- ‘maxUpto[maxStack.top]’ = ‘i’ - 1
- ‘maxStack.pop’
- ‘maxStack’.push(i)
- while ‘maxStack’ is not empty and ‘A[i]’ > ‘A[maxStack.top]’
- while ‘maxStack’ is not empty:
- ‘maxUpto[maxStack.top]’ = ‘N’ + ‘K’ - 1
- ‘maxStack.pop’
- Initialise a variable ‘j’ as 1.
- Loop through the dates from ‘i’ = 1’ to ‘i’ = ‘N’ :
- While (‘j’ < ‘i’ or ‘maxUpto[j]’ < ‘i’ + ‘K’ - 1) :
- ‘j’ = ‘j’ + 1
- ‘maxSum’ = ‘maxSum’ + ‘A[j]’
- While (‘j’ < ‘i’ or ‘maxUpto[j]’ < ‘i’ + ‘K’ - 1) :
- Return