题目描述

一个厨师收集了他 n 道菜的满意程度 satisfaction，这个厨师做出每道菜的时间都是 1 单位时间。

一道菜的 喜爱时间 系数定义为烹饪这道菜以及之前每道菜所花费的时间乘以这道菜的满意程度，也就是 time[i]*satisfaction[i]。

请你返回做完所有菜 喜爱时间 总和的最大值为多少。

你可以按 任意 顺序安排做菜的顺序，你也可以选择放弃做某些菜来获得更大的总和。

样例

输入：satisfaction = [-1,-8,0,5,-9]
输出：14
解释：去掉第二道和最后一道菜，最大的喜爱时间系数和为 (-1*1 + 0*2 + 5*3 = 14)。
每道菜都需要花费 1 单位时间完成。

输入：satisfaction = [4,3,2]
输出：20
解释：按照原来顺序相反的时间做菜 (2*1 + 3*2 + 4*3 = 20)

输入：satisfaction = [-1,-4,-5]
输出：0
解释：大家都不喜欢这些菜，所以不做任何菜可以获得最大的喜爱时间系数。

输入：satisfaction = [-2,5,-1,0,3,-3]
输出：35

限制

• n == satisfaction.length
• 1 <= n <= 500
• -10^3 <= satisfaction[i] <= 10^3

算法

(贪心，动态规划) $O(n^2)$

1. 将满意程度从小到大排序。这是因为不满意的菜要尽可能先做，这样损失会比较小，而后边得到的收益会更大，这个贪心可以自己通过交换的方式证明。
2. 设状态 $f(i, j)$ 表示前 $i$ 个菜，做了 $j$ 份的最大喜爱时间。假设菜的下标从 1 开始。
3. 初始时，$f(0, 0) = 0$，其余为负无穷。
4. 转移时，对于 $f(i, j)$，如果做第 $i$ 道菜，则总的喜爱时间为 $f(i - 1, j - 1) + j * s(i)$；如果放弃，则总的喜爱时间为 $f(i - 1, j)$。二者取最大值转移。
5. 最终答案为 $\max(f(n, j))$，其中 $0 \le j \le n$。

时间复杂度

• 排序的时间复杂度为 $O(n \log n)$。
• 动态规划的状态数为 $O(n^2)$，每次转移仅需要常数时间。
• 故总时间复杂度为 $O(n^2)$。

空间复杂度

• 需要额外 $O(n^2)$ 的空间存储状态。

C++ 代码

class Solution {
public:
    int maxSatisfaction(vector<int>& satisfaction) {
        sort(satisfaction.begin(), satisfaction.end());
        int n = satisfaction.size();

        vector<vector<int>> f(n + 1, vector<int>(n + 1, INT_MIN));
        f[0][0] = 0;

        for (int i = 1; i <= n; i++) {
            f[i][0] = f[i - 1][0];
            for (int j = 1; j <= i; j++)
                f[i][j] = max(f[i - 1][j], f[i - 1][j - 1] + j * satisfaction[i - 1]);
        }

        int ans = INT_MIN;
        for (int j = 0; j <= n; j++)
            ans = max(ans, f[n][j]);

        return ans;
    }
};