1402. Reducing Dishes

题目信息

题号:

1402

难度:

Hard

主题:

贪心、排序、前缀和

原题:

LeetCode 1402

重点:

可以舍弃任意菜并重新排序;第 i 道完成的菜贡献 satisfaction * i,最大化总和

题目重述

给定数组 satisfaction,其中每个元素表示一道菜的满意度。可以选择任意子集并按任意顺序烹饪,烹饪每道菜耗时一个单位。

若一道菜在第 i 个时间单位完成,其贡献为 satisfaction * i,时间从 1 开始。请返回所有选择与排列方案中最大的总满意度;允许一道菜都不做并得到 0。

1 <= satisfaction.length <= 500,-1000 <= satisfaction[i] <= 1000。

自建示例

适当保留负满意度菜也可能提高总和:

输入:satisfaction = [-2,5,-1]
输出:11
解释:按 -2、-1、5 的顺序烹饪,贡献为 -2 - 2 + 15 = 11。

全部满意度为负时选择空集:

输入:satisfaction = [-2,-1]
输出:0
解释:制作任意非空菜集都会得到负总和。