Problem statement

https://leetcode.com/problems/reducing-dishes/

Solution 1

Note first of all that we always need to take dishes with increasing satisfaction levels. define dp(i, c), where i is reached dish, c is coefficient of satisfaction. On each step we either dake dish or not.

Complexity

It is O(n^2) for time and space

Code

class Solution:
    def maxSatisfaction(self, S):
        @lru_cache(None)
        def dp(i, c):   #i is reached dish, c is coefficient
            if i == -1: return -abs(c)*100000
            return max(dp(i - 1, c - 1) + c*S[i], dp(i - 1, c))
        
        S, n = sorted(S), len(S)
        return max(dp(n - 1, c) for c in range(n + 1))

Solution 2

There is also O(n log n) time complexity solution, where we use the idea of accumulate sums: we need to sort data and then take the biggest one A1, then we add (A1 + A2) if it is positive, then add (A1 + A2 + A3) and so on.

Complexity

Code

class Solution:
    def maxSatisfaction(self, S):
        return max(0, max(accumulate(accumulate(sorted(S)[::-1]))))