N-dates with Lili

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
2 upvotes

Problem statement

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
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
4 2
1 2 3 4 5
3 1
9 8 7
Sample Output 1 :
14
24
Explanation Of Sample Input 1 :
For test 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.
On the 3rd date, they can go to restaurant 3 or restaurant 4.
On the 4th date, they can go to restaurant 4 or restaurant 5.

Among all possible combinations of restaurants, the following is the combination with the maximum total number of coins :
Date 1: restaurant 2
Date 2 : restaurant 3
Date 3 : restaurant 4
Date 4 : restaurant 5
Maximum total number of coins = 2 + 3 + 4 + 5 = 14

For test 2:
On the 1st date, they can only go to restaurant 1.
On the 2nd date, they can only go to restaurant 2.
On the 3rd date, they can only go to restaurant 3.

Maximum Total number of coins = 9 + 8 + 7 = 24
Sample Input 2 :
1
4 2
1 1 1 1 1
Sample Output 2 :
4
Hint

You need maximum coins for each date to calculate the maximum total number of coins.

Approaches (2)
Brute Force

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

O(N * K), where ‘N’ is the number of dates and ‘K’ is the number of restaurants they can go to on each date.

 

Since we are calculating the maximum of ’K’ elements for every date from 1 to ‘N’. So the overall Time Complexity is O(N * K).

Space Complexity

O(1)
 

We have only used temporary integer variables. So, the Space Complexity is constant, i.e. O(1).

Code Solution
(100% EXP penalty)
N-dates with Lili
Full screen
Console