Reducing Dishes

hard array dp greedy sorting

Problem

satisfaction[i] is the like-coefficient of dish i. Choose any subset and serve them in any order; total = Σ time × satisfaction (time starts at 1). Maximize total.

Inputsatisfaction = [-1,-8,0,5,-9]

Output14

Drop -8, -9; serve -1,0,5 → 1×-1 + 2×0 + 3×5 = 14.

satisfaction

def max_satisfaction(satisfaction):
    a = sorted(satisfaction)
    suf = total = 0
    for x in reversed(a):
        if suf + x <= 0: break
        suf += x; total += suf
    return total

function maxSatisfaction(satisfaction) {
  const a = satisfaction.slice().sort((x, y) => x - y);
  let suf = 0, total = 0;
  for (let i = a.length - 1; i >= 0; i--) {
    if (suf + a[i] <= 0) break;
    suf += a[i]; total += suf;
  }
  return total;
}

class Solution {
    public int maxSatisfaction(int[] s) {
        Arrays.sort(s);
        int suf = 0, total = 0;
        for (int i = s.length - 1; i >= 0; i--) {
            if (suf + s[i] <= 0) break;
            suf += s[i]; total += suf;
        }
        return total;
    }
}

int maxSatisfaction(vector& s) {
    sort(s.begin(), s.end());
    int suf = 0, total = 0;
    for (int i = (int)s.size() - 1; i >= 0; i--) {
        if (suf + s[i] <= 0) break;
        suf += s[i]; total += suf;
    }
    return total;
}

Explanation

Each dish you keep is multiplied by its serving time, and earlier dishes get smaller multipliers. The smart move is to sort ascending and serve the chosen dishes in that order, so the biggest like-coefficients get the biggest time multipliers.

Here is the key trick: adding one more dish at the front of your current chosen list bumps every already-chosen dish up by one time slot. That means including a new dish adds the new dish's value plus the entire running suffix sum to the total — so we can think in terms of a growing suf.

We scan from the largest value to the smallest. Each step we tentatively add a[i] to suf; as long as suf + a[i] stays positive, the dish helps, so we accept it and add the new suf into total. The moment it would drop to zero or below, every remaining (smaller) dish would only hurt, so we stop.

Example: satisfaction = [-1, -8, 0, 5, -9]. Sorted it is [-9, -8, -1, 0, 5]. Scanning from the right we keep 5, 0, and -1 but stop at -8. That gives 1×(-1) + 2×0 + 3×5 = 14.

Sorting dominates the cost, so the whole thing runs in O(n log n) with just two running counters.

Time: O(n log n) Space: O(1)