Max Profit
IBM● HardNEW GRADOAProblem statement
Find the maximum profit that can be generated for the given amount of money. As the answer can be rather large, report the answer as maxProfit % (10 ^ 9 + 7) where % denotes modulo operator.
Complete the function maxProfit in the editor.
maxProfit has the following parameters:
int[] cost: an array of integers representing the cost of each itemint x: the initial amount of money Walker has
int: the maximum profit that can be obtained modulo (10^9+7)
Function
maxProfit(cost: int[], x: int) → intExamples
Example 1
cost = [3, 4, 1]x = 8return = 7:)
Example 2
cost = [19, 78, 27, 15, 20]x = 25return = 16Walker can afford item 4, whose cost is 20 and whose profit is 2^4 = 16. After buying it, only 5 remains, so none of items 0 through 3 can also be purchased. Any combination that excludes item 4 has profit at most 2^0 + 2^1 + 2^2 + 2^3 = 15. Therefore, the maximum profit is 16.
Example 3
cost = [10, 20, 14, 40, 50]x = 70return = 20Some possible combination of items Walker can buy are: She can buy items 0, 1, and 2 for a cost of 44 and obtain a profit of 2 ^ 0 + 2 ^ 1 + 2 ^ 2 = 7. She can buy items 0 and 4 for a cost of 60 and obtain a profit of 2 ^ 0 + 2 ^ 4 = 17. She can buy items 1 and 4 for a cost of 70 and obtain a profit of 2 ^ 1 + 2 ^ 4 = 18. She can buy items 2 and 4 for a cost of 64 and obtain a profit of 2 ^ 2 + 2 ^ 4 = 20. Out of all the possible combinations, the maximum profit obtained is by buying items 2 and 4 for a cost of 64 to obtain a profit of 20.
Constraints
1 <= n <= 10^51 <= cost[i] <= 10^50 <= x <= 10^9