leetcode 1402. Reducing Dishes（减少菜肴）

satisfaction数组表示每道菜的喜爱程度, 有正有负。

做一个菜要1个单位的时间，但是要包含它前面的菜的时间，
也就是说第一道菜需要1单位时间，第2道菜2单位时间，第3道菜3单位时间，依次类推。

like-time系数 = 做菜时间 * satisfaction[i]。

可以按照任意顺序做菜（做菜时间也会发生变化）。
可以选择舍弃一些菜（不做），求最大的like-time系数之和。

思路：

首先整理一下，
做菜的顺序不同，那么每道菜的时间也不同，按顺序做菜时间是1,2,3,…,n.
like-time系数是做菜时间 * 满意度，
所以like-time系数之和就是1 * satisfaction[0] + 2 * satisfaction[1] + … + n * satisfaction[n-1].

因为要求最大的like-time系数和，所以正数的satisfaction是一定要保留的，
需要舍弃的是负数部分。
需要先把satisfaction数组排序，让负数靠左，正数靠右。

那么先求正数部分的like-time系数和，再一步一步地左移到负数部分，
系数和是单调递减的，当like-time系数和开始变小时，即得到最大的系数和。

但是这样每左移一步就需要计算一次系数和（因为做菜时间在变），
又是乘又是加，计算量显然太大。
就需要把这个式子化简，其实就变成了数学问题。

下面把satisfaction简称为s,
由于已经排过序，满意度最大的在最右边，时间最大的也在最右边，所以从右到左遍历数组，
满意度的累积和记作accum. 当前的like-time系数和记作cur.

i = n-1：accum = 0, cur = s[n-1] * 1
i = n-2：accum = s[n-1],
              cur = s[n-2] * 1 + s[n-1] * 2
                    = 前一个cur + accum + s[i]
i = n-3: accum = s[n-1] + s[n-2],
             cur = s[n-3] * 1 + s[n-2] * 2 + s[n-1] * 3
                   =s[i] + ( s[n-1] + s[n-2] ) + ( s[n-2] * 1 + s[n-1] * 2 )
                   = 前一个cur + accum + s[i]

    public int maxSatisfaction(int[] satisfaction) {
        int n = satisfaction.length;
        int accum = 0;
        int cur = 0;
        int maxV = 0;

        Arrays.sort(satisfaction);

        for(int i = n-1; i >= 0; i--) {
            cur = cur + accum + satisfaction[i];
            //if(cur < maxV) break; //加上更慢
            maxV = Math.max(maxV, cur);
            accum += satisfaction[i];
        }
        return maxV;
    }

上面的accum是从0开始，如果accum从s[n-1]开始，
那么每一步accum += s[i], cur += accum.

    public int maxSatisfaction(int[] satisfaction) {
        int n = satisfaction.length;
        int accum = 0;
        int cur = 0;
        int maxV = 0;

        Arrays.sort(satisfaction);

        for(int i = n-1; i >= 0; i--) {
            accum += satisfaction[i];
            cur += accum;
            //if(cur < maxV) break;
            maxV = Math.max(maxV, cur);
        }
        return maxV;
    }