1402. Reducing Dishes ===================== 题目信息 -------- :题号: 1402 :难度: Hard :主题: 贪心、排序、前缀和 :原题: `LeetCode 1402 `_ :重点: 可以舍弃任意菜并重新排序;第 ``i`` 道完成的菜贡献 ``satisfaction * i``,最大化总和 题目重述 -------- 给定数组 ``satisfaction``,其中每个元素表示一道菜的满意度。可以选择任意子集并按任意顺序烹饪,烹饪每道菜耗时一个单位。 若一道菜在第 ``i`` 个时间单位完成,其贡献为 ``satisfaction * i``,时间从 ``1`` 开始。请返回所有选择与排列方案中最大的总满意度;允许一道菜都不做并得到 ``0``。 ``1 <= satisfaction.length <= 500``,``-1000 <= satisfaction[i] <= 1000``。 自建示例 -------- 适当保留负满意度菜也可能提高总和: .. code-block:: text 输入:satisfaction = [-2,5,-1] 输出:11 解释:按 -2、-1、5 的顺序烹饪,贡献为 -2 - 2 + 15 = 11。 全部满意度为负时选择空集: .. code-block:: text 输入:satisfaction = [-2,-1] 输出:0 解释:制作任意非空菜集都会得到负总和。