# Running sum

1 min readApr 4, 2020

--

# 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