1402.md

1402. Reducing Dishes

Solution 1 (time O(nlog(n)), space O(n))

class Solution(object):
    def maxSatisfaction(self, satisfaction):
        """
        :type satisfaction: List[int]
        :rtype: int
        """
        satisfaction.sort(reverse=True)
        ans = 0
        prefix_sum = 0
        for t in satisfaction:
            prefix_sum += t
            if prefix_sum <= 0:
                break
            ans += prefix_sum
        return ans