1402. Reducing Dishes

class Solution:
    def maxSatisfaction(self, A: List[int]) -> int:
        """ tc O(NlgN) sc O(1)
        main idea: start with the biggest satisfaction level;  as only as current accumutive satisfaction >0, the longer biggest dish stays, the more coefficiency total will get
        => need to track (1) accumutive satisfaction :  = total + A[i](2) total coefficiency : each time  res += total   
        1. sort ascending 
        2. track accumutive satisfaction  
        3. keep add accumu onto total until acuumutive < 0  , return 
        """
        res = cur = 0
        A.sort()
        n = len(A)
        i = n-1 
        while i >=0 and cur + A[i] >0:  
            cur += A[i]
            res += cur
            i -= 1 
        return res 
        ######################### optimal way to write it 
        res = cur = 0
        A.sort()
        n = len(A)
        while A and A[-1] + cur > 0 :
            cur+= A.pop()
            res += cur
        return res