1402. 做菜顺序

解法一：贪心

我自己只能想到贪心的做法了。
先根据满意程度的正负将菜分成两堆（0跟正数分在一起）。实际做菜的时候负数的菜先做，正数的菜后做。
正数堆的菜肯定是全部要做的，而且要按照满意程序升序来做，这样满意程度高的菜乘上的时间系数更大，总的结果也就更大。
负数堆的菜按照降序排列，有选择地做，每做一道菜便意味了后续的所有菜时间系数+1，所以要根据做这道菜带来的负收益和正收益之和是否大于0来决定是否做。

import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
class Solution {
    public int maxSatisfaction(int[] satisfaction) {
        // 正数堆, 包括0
        List<Integer> positive = new LinkedList<>();
        // 负数堆
        List<Integer> negative = new LinkedList<>();
        for (int i : satisfaction) {
            if (i >= 0) {
                positive.add(i);
            } else {
                negative.add(i);
            }
        }
        // 对正数升序排列
        Collections.sort(positive);
        // 对负数降序排列
        Collections.sort(negative, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        // 时间系数
        int time = 0;
        // 总满意度
        int ans = 0;
        // 正收益
        int sum = 0;
        for (Integer i : positive) {
            ans += (++time) * i;
            sum += i;
        }
        // 负收益
        int sum_ = 0;
        for (Integer i : negative) {
            sum_ += i;
            if (sum + sum_ < 0) {
                break;
            }
            ans += sum + sum_;
        }
        return ans;
    }
}

解法二：贪心

总体思路同解法一，写复杂了😅。
不判断小于0的话也可以写成DP的形式。

import java.util.Arrays;
class Solution {
    public int maxSatisfaction(int[] satisfaction) {
        Arrays.sort(satisfaction);
        int ans = 0;
        for (int i = satisfaction.length - 1, sum = 0; i >= 0; --i) {
            sum += satisfaction[i];
            if (sum < 0) {
                break;
            }
            ans += sum;
        }
        return ans;
    }
}