# 【LeetCode】 1402. Reducing Dishes

## Description

> 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.

> Constraints:
> `n == satisfaction.length`
> `1 <= n <= 500`
> `-1000 <= satisfaction[i] <= 1000`

> 一個廚師收集了他 `n` 盤菜餚的 `satisfaction` (滿意度)等級數據。廚師可以在一個單位時間內完成一道任意的菜餚。
> 一道菜餚的喜歡時間係數定義為烹煮這道菜餚（包含之前所有菜餚）花費的時間乘上菜餚的滿意度。也就是 `time[i] * satisfaction[i]` (時間[i] * 滿意度[i])。
> 回傳廚師準備菜肴後可獲得的最大喜歡時間係數之和。
> 菜餚可以按照任意順序做準備，廚師也可以捨棄任意數量的菜餚以獲得最大值。

> 限制：
> `n == satisfaction.length`
> `1 <= n <= 500`
> `-1000 <= satisfaction[i] <= 1000`

## Example:

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.

## Solution

* 題目有些拗口實際上就是
* 給一陣列，可隨意改變順序，甚至可隨意丟棄元素
* 改變完陣列後，第一個元素乘一加上第二的元素乘二...求總和最大為多少
* 第一個直覺的想法是只留下非負數，但其實這是錯的，因為將小的負數放在前面可以使後面的正數加更多，因此要策略性地留下負數
* 例如第一個範例測資
* 一個關鍵的想法是最後答案的陣列一定會按照大小排序，因此我們可以將陣列先排序，然後思考要拿多少負數
* 我們每加一個負數到陣列時，喜歡時間係數(答案)會如何改變？
* 加上目前陣列的總和和加入的負數
* 因此要將答案最大化，就是目前陣列總和大於零就可以繼續拿負數，反之則停止

---

* 感謝實驗室的小夥伴們與我一起完成這題

### Code

class Solution {
public:
    int maxSatisfaction(vector<int>& satisfaction) {
        int sum = 0;
        int ans = 0;
        sort(satisfaction.rbegin(), satisfaction.rend());

        for(int i = 0; i < satisfaction.size(); i++)
        {
            sum += satisfaction[i];
            if(sum < 0)
                break;
            ans += sum;
        }
        return ans;
    }
};

###### tags: `LeetCode` `C++`