# 1402. Reducing Dishes
###### tags: `Leetcode` `Hard` `Greedy` `Sorting`
Link: https://leetcode.com/problems/reducing-dishes/description/
## 思路
以```satisfaction = [-1,-8,0,5,-9]```为例
首先想到我们肯定是把越大的数字放在越后面越好 因此我们需要排序
得到```[-9, -8, -1, 0, 5]```
接着想到如果我们从后往前遍历所有可能的答案才能找到最优解
所以我们需要依次计算

5*1
5*2+0*1
5*3+0*2+(-1)*1
...

我们会发现每次增长的数目都是这个array的postsum
所以我们只需要先放postsum 每次都加在curr上面 然后取最大值即可
## Code

class Solution {
    public int maxSatisfaction(int[] satisfaction) {
        Arrays.sort(satisfaction);
        int n = satisfaction.length;
        int[] prefix = new int[n];
        prefix[n-1] = satisfaction[n-1];
        for(int i=n-2; i>=0; i--){
            prefix[i] = prefix[i+1]+satisfaction[i];
        }
        int ans = 0;
        int curr = 0;
        for(int i=n-1; i>=0; i--){
            curr += prefix[i];
            ans = Math.max(ans, curr);
        }
        return ans;
    }
}