Running sum

1402. Reducing Dishes

A naive solution to this problem is brute force.

Sorting and check. It has the time complexity of O(n²) and space complexity of O(n²) as the satisfaction[I:]. Since n is only 500, it is an AC solution.

class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        satisfaction.sort()
        if satisfaction[-1]<=0:return 0
        res = -float('inf')
        N = len(satisfaction)
        for i in range(N):
            this_res = sum(a*b for a,b in zip(range(1, N-i+1),satisfaction[i:]))
            res =  max(res, this_res)
            if satisfaction[i]>=0:break
        return res

Running sum

Something I learned from lee215'’s post is running sum. Time complexity is O(n log n) and the space complexity is O(1)

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