1402.Reducing Dishes
===

###### tags: `Hard`,`Array`,`DP`,`Greedy`,`Sorting`

[1402. Reducing Dishes](https://leetcode.com/problems/reducing-dishes/)

### 題目描述

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**:

* 1 <= `days.length` <= 365
* 1 <= `days[i]` <= 365
* `days` is in strictly increasing order.
* `costs.length` == 3
* 1 <= `costs[i]` <= 1000

### 解答
#### Python
作法: Greedy，先對菜餚做排序，價值越高的菜餚要累加越多次，直到當前滿意度 < 0 時，則停止計算

class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        satisfaction = sorted(satisfaction)
        suffix_sum, max_satisfaction = 0, 0
        
        for i in range(len(satisfaction) - 1, -1, -1):
            if suffix_sum + satisfaction[i] > 0:
                suffix_sum += satisfaction[i]
                max_satisfaction += suffix_sum

        return max_satisfaction

> [name=Ron Chen][time=Wed, Mar 29, 2023]

class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        satisfaction.sort(reverse=True)
        total, ans = 0, 0
        for value in satisfaction:
            if total + value <= 0: break
            total += value
            ans += total
        return ans

> [name=Yen-Chi Chen][time=Wed, Mar 29, 2023]

class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        satisfaction.sort(reverse=True)
        if satisfaction[0] <= 0:
            return 0

        total = 0
        max_value = 0
        for i, _ in enumerate(satisfaction):
            total = sum([(i-j+1)*satisfaction[j] for j in range(i+1)])
            if total > max_value:
                max_value = total

        return max_value

> [name=gpwork4u][time=Thur, Mar 30, 2023]

#### C++

class Solution {
public:
    int maxSatisfaction(vector<int>& satisfaction) {
        sort(satisfaction.begin(), satisfaction.end(), greater<int>());
        int sum = 0, ans = 0;
        for (auto value : satisfaction) {
            sum += value;
            if (sum <= 0) break;
            ans += sum;
        }
        return ans;
    }
};

> [name=Yen-Chi Chen][time=Wed, Mar 29, 2023]

#### Javascript

function maxSatisfaction(satisfaction) {
  satisfaction.sort((a, b) => b - a);
  let max = 0;
  let sum = 0;
  for (const num of satisfaction) {
    sum += num;
    if (sum > 0) {
      max += sum;
    } else {
      break;
    }
  }

  return max;
}

> [name=Marsgoat][time=Wed, Mar 29, 2023]
### Reference

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)