A chef has collected data on the satisfaction level of his n dishes. Chef can cook any dish in 1 unit of time.
Like-time coefficient of a dish is defined as the time taken to cook that dish including previous dishes multiplied by its satisfaction level i.e. 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: 14 Explanation: After Removing the second and last dish, the maximum total like-time coefficient will be equal to (-1*1 + 0*2 + 5*3 = 14). Each dish is prepared in one unit of time.
Example 2:
Input: satisfaction = [4,3,2] Output: 20 Explanation: Dishes can be prepared in any order, (2*1 + 3*2 + 4*3 = 20)
Example 3:
Input: satisfaction = [-1,-4,-5] Output: 0 Explanation: People do not like the dishes. No dish is prepared.
Constraints:
n == satisfaction.length1 <= n <= 500-1000 <= satisfaction[i] <= 1000To maximize the like-time coefficient, we can sort the satisfaction levels in non-descending order and calculate the possible like-time coefficients by considering prefixes from the end of the sorted array. This allows us to selectively choose higher satisfaction dishes to maximize the total like-time coefficient.
This C program sorts the satisfaction array in decreasing order and iteratively calculates the like-time coefficient. If adding the current satisfaction level to the sum results in a non-positive value, the computation stops as it indicates that further additions would only decrease the total result.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) for using a constant amount of extra space.
An alternative approach involves using dynamic programming to maximize the like-time coefficient. We maintain a DP table where `dp[i]` represents the maximum like-time coefficient attainable using the first `i` dishes. This approach computes overlap coefficients dynamically using state transitions calculated for each dish considered.
This C solution employs dynamic programming by initializing a DP array with zero and iteratively updating it by considering the choice of including a dish or not, thereby maximizing the like-time coefficient.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2)
Space Complexity: O(n)
| Approach | Complexity |
|---|---|
| Approach 1: Sorting and Selecting Positive Coefficients | Time Complexity: O(n log n) due to sorting. |
| Approach 2: Dynamic Programming | Time Complexity: O(n^2) |
Lecture 118: Reducing Dishes LeetCode || 2D-DP || DP Series • CodeHelp - by Babbar • 38,630 views views
Watch 9 more video solutions →Practice Reducing Dishes with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor