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.
def maxSatisfaction(self, satisfaction: List[int]) -> int:
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)
Something I learned from lee215'’s post is running sum. Time complexity is O(n log n) and the space complexity is O(1)
def maxSatisfaction(self, A):
res = total = 0
while A and A[-1] + total > 0:
total += A.pop()
res += total