Running sum

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

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store