Reducing Dishes
A chef has collected data on the satisfaction level of his n dishes. The chef can cook any dish in 1 unit of time.
The like-time coefficient of a dish is defined as the time taken to cook that dish, including previous dishes, multiplied by its satisfaction level: time[i] * satisfaction[i].
Return the maximum sum of like-time coefficient that the chef can obtain after preparing some amount of dishes.
Dishes can be prepared in any order, and the chef can discard some dishes to get this maximum value.
Example 1
Input
satisfaction = [-1,-8,0,5,-9]Output
14After removing the second and last dish, the maximum total like-time coefficient is
-1 * 1 + 0 * 2 + 5 * 3 = 14.Example 2
Input
satisfaction = [4,3,2]Output
20Dishes can be prepared in the order
[2, 3, 4], giving 2 * 1 + 3 * 2 + 4 * 3 = 20.Constraints
- n == satisfaction.length
- 1 <= n <= 500
- -1000 <= satisfaction[i] <= 1000
Asked at 2 companies
Practice questions like this out loud in a mock coding interview with a live AI interviewer. First one free.