# Leetcode 1402. Reducing Dishes
給定n道菜餚array名叫satisfaction,你可以按照任何順序挑選,則需要得到最大的價值,價值算法為,你第幾個挑選到的菜餚的計數*該菜餚的水平，想出解決方案,讓該價值為最大。

## 想法
因為可以按照任何順序選取,所以水平較高的菜餚理應比較慢選,以得到較高的計數價值,所以我們先將satisfaction從大到小排序,再開始拿取。
1.首先 我們設定3個變數
best:為最佳解,也是我們最後的答案。
total:紀錄目前總答案。
esum:目前加入新的菜餚是否對於total的增加有幫助。
當esum為負時代表,接下來選擇菜餚都沒辦法使best增加,則可以跳出。

證明,以[3,2,1]為例：
第一個周期：
esum = 3
total = 3
best = 3
第二個周期：
esum = 3+2 = 5
total = 3+5 = 8 (因為重複加esum所以會得到 3*2+2*1的結果)
best = 8
第三個周期：
esum = 3+2+1 = 6
total = 3+5+6 = 14 (因為重複加esum所以會得到 3*3+2*2+1*1的結果)
best = 14

特別的點為esum的計算,因為累加的性質,造成前面的計數的乘數不斷+1的狀態完美的解決這題的題幹。

程式碼:

def maxSatisfaction(self, satisfaction: List[int]) -> int:
        satisfaction.sort(reverse=True)
        best,esum,total = 0,0,0
        for x in satisfaction:
            esum  += x
            total += esum
            best = max(total,best)
            if esum<0:
                break
        return best