Reducing Dishes — LeetCode 1402 Python Solution

The problem

A chef has collected data on the satisfaction level of his n dishes. Chef can cook any dish in 1 unit of time.

Example

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).

Python solution

class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        satisfaction.sort(reverse=True)
        ans = s = 0
        for x in satisfaction:
            s += x
            if s <= 0:
                break
            ans += s
        return ans

Complexity

Pattern: Greedy

Take the locally best option every time — when you can prove that never costs you later. LeetCode 1402. Reducing Dishes is filed here because LeetCode tags it Greedy, which is the vocabulary this hub collects.

The greedy guide has the Python template for the pattern and the 346 LeetCode problems that use it.

Related problems