# Leetcode 1402. Reducing Dishes
###### tags: `leetcode` `daily`

[題目連結](https://leetcode.com/problems/reducing-dishes/)

# Method Greedy
:::info
:bulb: **作法講解**:

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

we can list some example:

case 1:
if `a, b, c` is positive number, and `c > b > a`
`1 * a + 2 * b + 3 * c` is maximum value,

case 2:
if `a` is negative number, `b, c` is positive number, and `c > b > a`
we may have two choice.
choice 1: `1 * a + 2 * b + 3 * c`
choice 2: `1 * b + 2 * c`

as above idea,

1. we can sort the array from largest to smallest,
2. `array = [a0, a1, a2, a3, a4...], a0 > a1 > a2 > a3 > a4 `
2.1 `1 * a0`
2.2 `2 * a0 + 1 * a1`
2.3 `3 * a0 + 2 * a1 + 1 * a3`
2.4 `4 * a0 + 3 * a1 + 2 * a3 + 1 * a4`
check 2.1 ~ 2.4 which sum is maximum sum.
:::

TC: O(NlogN) SC: O(1)
完整程式碼

class Solution {
public:
    int maxSatisfaction(vector<int>& satisfaction) {
        int n = satisfaction.size();
        int output = 0;
        int last = 0;
        int sum = 0;
        sort(satisfaction.rbegin(), satisfaction.rend());
        for(int i = 0 ; i < n ; i++) {
            sum += satisfaction[i];
            last += sum;
            output = max(output, last);
        }
        return output;
    }
};