Maximum Profit

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
1 upvote
Asked in company
Cashfree Payments

Problem statement

Bob has joined a part-time job as a delivery man. He needs to deliver ‘N’ packages with ‘A[i]’ value within ‘K’ days.

In one day, Bob can deliver as many packages as he wants, but the ‘i’th package cannot be delivered until ‘(i - 1)’th package is not delivered.

Each day, Bob earns the maximum value of the packages Bob delivered during that day.

Can you help Bob to find a way to deliver his packages to maximize his earning?

Note: If Bob does not deliver any packages someday, his earning will be 0 on that day.

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

The first line of each test case contains two space-separated integers, ‘N’ & ‘K’.

The following line contains ‘N’ space-separated integers denoting the array ‘A’.
Output Format: 
For each test case, print an integer denoting the maximum amount Bob can earn after all deliveries.
Note: 
You are not required to print the expected output. It has already been taken care of. Just implement the function.
Constraints: 
1 <= T <= 5
1 <= K <= N <= 10^5
1 <= A[i] <= 10^9

Time Limit: 1 sec
Sample Input 1:
2
5 1
1 2 3 4 5
5 5
1 2 3 4 5
Sample Output 1:
5
15
Explanation for Sample Input 1:
In the first test case, Bob will deliver all packages on the first day, so his earning will be max(1, 2, 3, 4, 5) = 5.

In the second test case, Bob will deliver one package each day, so his earning will be 1 + 2 + 3 + 4 + 5 = 15.
Sample Input 2:
2
6 3
7 7 7 7 7 7
5 5
1 2 3 7 8
Sample Output 2:
21
21
Hint

Can we check the earnings for all possible configurations?

Approaches (3)
Brute Force

Iterate through every possible configuration and calculate the earning at each configuration. The maximum of those earnings will be our answer.

 

Algorithm:

  • Declare a helper function ‘solve’ which takes ‘N’, ‘K’, ‘A’ and a starting index ‘i’ as parameters. The solve function calculates the answer for the sub-array ‘A[i]’ to ‘A[N - 1]’ (0-based indexing).
  • Return ‘solve(N, K, A, 0)’.
  • In the function ‘solve’ :
    • If K == 0 or i == N
      • Return 0.
    • Initialize a variable ‘maxEarning’ as 0.
    • Initialize a variable ‘maxValue’ as 0.
    • Iterate from ‘j’ = ‘i’ to ‘N’.
      • Set ‘maxEarning’ as max(maxEarning, maxValue +  solve(N, K - 1, A, j).
      • If j < N
        • Set ’maxValue’ as max(maxValue, A[j]).
    • Return ‘maxEarning’.
Time Complexity

O((N + K - 1)CN), where ‘N’ is the number of packages, and ‘K’ is the number of days.


There are (N + K - 1)CN possible configurations, and we are iterating through all of them.

Space Complexity

O(K), where K is the number of days.

 

There will be at most K function calls in the stack space for recursion at a given point of time.

Code Solution
(100% EXP penalty)
Maximum Profit
Full screen
Console