1402. Reducing Dishes

Hard

---

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.

Constraints:

• n == satisfaction.length

• 1 <= n <= 500

• -1000 <= satisfaction[i] <= 1000

Solution 1 : Greedy Solution , Time : O(NlogN)

class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        satisfaction.sort()
        total, result = 0, 0
        while satisfaction and total + satisfaction[-1] > 0:
            total += satisfaction.pop()
            result += total
        return result

Solution 2 : DP

class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        satisfaction.sort()
        length = len(satisfaction)
        result = 0
        dp = [[0]*(length+1) for _ in range(length)]
        for i in range(length):
            for j in range(i+1, length+1):
                dp[i][j] = dp[i][j-1] + (j-i)*satisfaction[j-1]
                result = max(result, dp[i][j])
        return result