Last Updated: 9 Oct, 2021
Maximum Profit
Moderate
Asked in company
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.
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
Approaches
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’.
- If K == 0 or i == N
Iterate through every possible configuration and calculate the earning at each configuration. The maximum of those earnings will be our answer.
We will reduce the time of execution with the help of memoization as there are overlapping subproblems.
Algorithm:
- Initialize a global variable ‘dp’ as a map of integer and map of integer and integer.
- 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.
- If dp[N - i][K] != 0
- Return dp[N - i][K].
- 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]).
- Set ‘dp[N - i][K]’ as ‘maxEarning’.
- Return ‘maxEarning’.
- If K == 0 or i == N
The maximum possible profit you can obtain is the sum of the given array’s ‘K’ largest values. We can always separate these ‘K’ maximums and then extend the segments corresponding to them to the left or the right and cover the entire array.
Algorithm:
- Initialize ‘ans’ as 0.
- Sort the array ‘A’.
- Add all numbers from ‘A[N - K]’ to ‘A[N - 1]’ (0-based indexing) to ‘ans’.
- Return ‘ans’.