vlambda博客
学习文章列表

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

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

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

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

示例 1：

输入：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

解释：大家都不喜欢这些菜，所以不做任何菜可以获得最大的喜爱时间系数。

在这题中每道菜的喜爱时间是每道菜的满意度*之前花费的时间，比如数组[5，6，7]，第一道菜的喜爱时间是1*5，第二道菜的喜爱时间是2*6，第三道菜的喜爱时间是3*7。但这题求的是最大值，并且还有负数，所以最简单的一种解决方式就是先对数组进行排序，我们从后往前开始计算，但这里有个问题，就是排序之后最后一道菜所花费的时间是多少，这里我们可以考虑使用后缀和，也就是从数组后面统计他们的和，这里以示例一为例画个图来看下

通过上面我们可以看到，当后缀和小于0的时候，相加的结果会越来越小，所以这题就可以转化为求后缀和问题，来看下代码

public int maxSatisfaction(int[] satisfaction) {
    // 先对数组进行排序
    Arrays.sort(satisfaction);
    // 因为是从数组的后面进行累加，这里记为后缀和
    int afterSum = 0;
    int res = 0;// 返回的结果
    for (int i = satisfaction.length - 1; i >= 0; i--) {
        // 从数组的后面累加，也就是后缀和
        afterSum += satisfaction[i];
        // 如果后缀和小于0，就终止计算，因为是排序的，
        // 前面会越加越小
        if (afterSum <= 0)
            return res;
        //累加后缀和
        res += afterSum;
    }
    return res;
}