# 1402. Reducing Dishes

#### Hard

***

A chef has collected data on the `satisfaction` level of his `n` dishes. Chef can cook any dish in 1 unit of time.

**Like-time coefficient** of a dish is defined as the time taken to cook that dish including previous dishes multiplied by its satisfaction level i.e. `time[i] * satisfaction[i]`.

Return *the maximum sum of **like-time coefficient** that the chef can obtain after dishes preparation*.

Dishes can be prepared in **any** order and the chef can discard some dishes to get this maximum value.

 

**Example 1:**

```
Input: satisfaction = [-1,-8,0,5,-9]
Output: 14
Explanation: After Removing the second and last dish, the maximum total like-time coefficient will be equal to (-1*1 + 0*2 + 5*3 = 14).
Each dish is prepared in one unit of time.
```

**Example 2:**

```
Input: satisfaction = [4,3,2]
Output: 20
Explanation: Dishes can be prepared in any order, (2*1 + 3*2 + 4*3 = 20)
```

**Example 3:**

```
Input: satisfaction = [-1,-4,-5]
Output: 0
Explanation: People do not like the dishes. No dish is prepared.
```

 

**Constraints:**

* `n == satisfaction.length`
* `1 <= n <= 500`
* `-1000 <= satisfaction[i] <= 1000`

#### Solution 1 : Greedy Solution , Time : O(NlogN)

```python
class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        satisfaction.sort()
        total, result = 0, 0
        while satisfaction and total + satisfaction[-1] > 0:
            total += satisfaction.pop()
            result += total
        return result
```

#### Solution 2 : DP

```python
class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        satisfaction.sort()
        length = len(satisfaction)
        result = 0
        dp = [[0]*(length+1) for _ in range(length)]
        for i in range(length):
            for j in range(i+1, length+1):
                dp[i][j] = dp[i][j-1] + (j-i)*satisfaction[j-1]
                result = max(result, dp[i][j])
        return result
```