[LeetCode] 1402. Reducing Dishes (Hard/Python)

Reducing Dishes - LeetCode

Above is the link to the problem

 

Problem

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 dishes preparation.

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.

 

Analysis

We can solve this by using dynamic programming.

From the example 1, the ascending order of satisfaction = [-9,-8,-1,0,5]

Maybe, to get the number of maximum dishes,

the maximum value of satisfaction should be added mostly.

temp = sum([5]) #temp = 5
temp += sum([0,5]) #temp = 10
temp += sum([-1,0,5]) #temp = 14
temp += sum([-8,-1,0,5]) #temp = 10
temp += sum([-9,-8,-1,0,5]) #temp = -3

 

Code

The time complexity of the code is O(n).

 

 

This code gets the top 41.77% of the time complexity and uses 14MB of memory.