Problem Description

You are given an array of integers sat where sat[i] represents the satisfaction level of the i-th dish. A chef can prepare any subset of these dishes in any order. For each dish prepared at time t (where t starts at 1 and increases by 1 for each subsequent dish), the chef gains t * sat[i] points of satisfaction.

The chef wants to maximize the total sum of satisfaction points by choosing an optimal subset and order of dishes. The chef may choose to discard some dishes (i.e., not prepare them at all).

Constraints:

• Each dish can be used at most once (no reuse).
• There is always at least one valid solution (possibly by skipping all dishes).
• The order of preparation matters for the final score.

Thought Process

At first glance, it might seem necessary to try every possible subset and permutation of the dishes, since both selection and ordering affect the result. However, this brute-force method quickly becomes infeasible due to the exponential number of possibilities.

To optimize, let's look for patterns:

• Preparing higher satisfaction dishes later multiplies their value by a higher time factor.
• Negative satisfaction dishes may decrease the total score, especially if prepared early.
• We want to maximize the weighted sum, so perhaps preparing higher satisfaction dishes later is beneficial.

Solution Approach

Let's break down the steps to solve this problem efficiently:

1. Sort the satisfaction array in ascending order.
   • This lets us consider negative and low-satisfaction dishes first, so we can decide whether including them helps or hurts the total.
2. Iterate from the highest satisfaction backwards.
   • Start with the dish with the highest satisfaction, and keep adding dishes one by one (moving backwards in the array).
3. Maintain a running total and cumulative sum.
   • For each dish added at the beginning, the cumulative satisfaction for all later dishes increases, since their time factor increases by 1.
   • If adding a dish increases the total satisfaction, keep it; otherwise, stop.
4. Return the maximum satisfaction found.

This greedy approach works because adding a negative satisfaction dish only helps if the increase in time factors for the remaining dishes outweighs the penalty from the negative value.

Example Walkthrough

Sample Input: sat = [-1, -8, 0, 5, -9]

1. Sort: [-9, -8, -1, 0, 5]
2. Start from the end (5): Try to include dishes one by one from right to left.
3. • Include 5: total = 5
   • Include 0: total = (5) + (0 + 5) = 5 + 5 = 10
   • Include -1: total = (-1) + (0) + (5) = -1 + 0 + 5 = 4 (but time factors apply: 1*-1 + 2*0 + 3*5 = -1 + 0 + 15 = 14)
   • But actually, by our greedy approach, we keep a cumulative sum and see if adding -1 increases the total.
   • Continue: Each time, check if the running total increases.
4. The maximum satisfaction is achieved by using [0, 5] or [-1, 0, 5], depending on the sum. The algorithm will find the optimal point to stop.

Time and Space Complexity

• Brute-force: O(n! * 2^n), since we would need to try all subsets and all permutations of each subset. This is not feasible for large n.
• Optimized Approach:
  • Sorting takes O(n log n).
  • The greedy iteration is O(n).
  • Total: O(n log n) time and O(1) extra space (if sorting in place).

Summary

The key insight is to sort the dishes by satisfaction and build the optimal subset backwards, always checking if including another dish increases the total satisfaction. This greedy method efficiently finds the best answer, avoiding the need to check all possible combinations and orders. By focusing on how time factors increase for each earlier dish, we elegantly maximize the final satisfaction score.

Code Implementation

class Solution:
    def maxSatisfaction(self, satisfaction):
        satisfaction.sort()
        total, res, curr = 0, 0, 0
        for sat in reversed(satisfaction):
            curr += sat
            if curr > 0:
                res += curr
            else:
                break
        return res
      

class Solution {
public:
    int maxSatisfaction(vector<int>& satisfaction) {
        sort(satisfaction.begin(), satisfaction.end());
        int res = 0, curr = 0;
        for (int i = satisfaction.size() - 1; i >= 0; --i) {
            curr += satisfaction[i];
            if (curr > 0) {
                res += curr;
            } else {
                break;
            }
        }
        return res;
    }
};
      

class Solution {
    public int maxSatisfaction(int[] satisfaction) {
        Arrays.sort(satisfaction);
        int res = 0, curr = 0;
        for (int i = satisfaction.length - 1; i >= 0; --i) {
            curr += satisfaction[i];
            if (curr > 0) {
                res += curr;
            } else {
                break;
            }
        }
        return res;
    }
}
      

var maxSatisfaction = function(satisfaction) {
    satisfaction.sort((a, b) => a - b);
    let res = 0, curr = 0;
    for (let i = satisfaction.length - 1; i >= 0; --i) {
        curr += satisfaction[i];
        if (curr > 0) {
            res += curr;
        } else {
            break;
        }
    }
    return res;
};