1402. Reducing Dishes

A naive solution to this problem is brute force.

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

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

Data Scientist/MLE/SWE @takemobi