# Reducing Dishes
**Difficulty:** HARD
[External](https://leetcode.com/problems/reducing-dishes)
Canonical: https://scaleengineer.com/dsa/problems/reducing-dishes
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [Sony](https://scaleengineer.com/companies/sony)
---
## Problem
A chef has collected data on the `satisfaction` level of his `n` dishes. Chef can cook any dish in 1 unit of time.

**Like-time coefficient** of a dish is defined as the time taken to cook that dish including previous dishes multiplied by its satisfaction level i.e. `time[i] * satisfaction[i]`.

Return the maximum sum of **like-time coefficient** that the chef can obtain after preparing some amount of dishes.

Dishes can be prepared in **any** order and the chef can discard some dishes to get this maximum value.

**Example 1:**

**Input:** satisfaction = [-1,-8,0,5,-9]
**Output:** 14
**Explanation:** After Removing the second and last dish, the maximum total **like-time coefficient** will be equal to (-1*1 + 0*2 + 5*3 = 14).
Each dish is prepared in one unit of time.

**Example 2:**

**Input:** satisfaction = [4,3,2]
**Output:** 20
**Explanation:** Dishes can be prepared in any order, (2*1 + 3*2 + 4*3 = 20)

**Example 3:**

**Input:** satisfaction = [-1,-4,-5]
**Output:** 0
**Explanation:** People do not like the dishes. No dish is prepared.

**Constraints:**

* `n == satisfaction.length`
* `1 <= n <= 500`
* `-1000 <= satisfaction[i] <= 1000`

# Approaches
## Dynamic Programming
This approach uses dynamic programming to solve the problem. After sorting the satisfaction array, we define a 2D DP table `dp[i][j]` to store the maximum like-time coefficient achievable by considering the first `i` dishes and choosing to cook exactly `j` of them. The state transition considers two choices for each dish: either cook it or don't cook it.
**Time:** O(n^2). Sorting takes O(n log n), and filling the n x n DP table takes O(n^2) time. · **Space:** O(n^2) for the 2D DP table. This can be optimized to O(n) because `dp[i]` only depends on `dp[i-1]`.
**Pros:** Provides a systematic way to explore all valid choices.; Guaranteed to find the optimal solution.
**Cons:** Has a time complexity of O(n^2), which is slower than the optimal greedy approach.; Requires O(n^2) space for the DP table, which is inefficient for large `n` (though can be optimized to O(n)).; The logic is less intuitive compared to the greedy solution.
### Explanation
First, we sort the `satisfaction` array. This is a critical step because for any chosen set of dishes, the optimal strategy to maximize the like-time coefficient is to cook them in increasing order of their satisfaction. This gives larger time multipliers to dishes with higher satisfaction.

After sorting, we can define a dynamic programming state. Let `dp[i][j]` be the maximum like-time coefficient using `j` dishes from the first `i` dishes of the sorted array (`satisfaction[0...i-1]`).

The recurrence relation is as follows:
`dp[i][j] = max(dp[i-1][j], dp[i-1][j-1] + satisfaction[i-1] * j)`

- The term `dp[i-1][j]` represents the case where we decide **not** to cook the `i`-th dish (`satisfaction[i-1]`). The maximum sum is then the best we could do with the first `i-1` dishes, still cooking a total of `j` dishes.
- The term `dp[i-1][j-1] + satisfaction[i-1] * j` represents the case where we **do** cook the `i`-th dish. Since it has the highest satisfaction among the `j` dishes chosen so far (due to sorting), it will be cooked at time `j`. The other `j-1` dishes must be chosen from the first `i-1` dishes, which gives a sum of `dp[i-1][j-1]`. We add the contribution of the current dish, which is `satisfaction[i-1] * j`.

The base case is `dp[i][0] = 0` for all `i`, as cooking zero dishes yields a coefficient of 0. The final answer is the maximum value found in the last row of the DP table, `max(dp[n][j])` for `0 <= j <= n`, since we can choose to cook any number of dishes from 0 to `n`.

```java
import java.util.Arrays;

class Solution {
    public int maxSatisfaction(int[] satisfaction) {
        int n = satisfaction.length;
        Arrays.sort(satisfaction);
        
        // dp[i][j]: max satisfaction considering first i dishes and cooking j of them
        int[][] dp = new int[n + 1][n + 1];
        // Initialize with a very small value to handle negative satisfactions
        for (int[] row : dp) {
            Arrays.fill(row, Integer.MIN_VALUE / 2); // Avoid overflow on addition
        }
        
        // Base case: cooking 0 dishes gives 0 satisfaction
        for (int i = 0; i <= n; i++) {
            dp[i][0] = 0;
        }
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                // Option 1: Cook the current dish (satisfaction[i-1])
                // This will be the j-th dish cooked.
                int cook = dp[i - 1][j - 1] + satisfaction[i - 1] * j;
                
                // Option 2: Don't cook the current dish
                int skip = dp[i - 1][j];
                
                dp[i][j] = Math.max(cook, skip);
            }
        }
        
        int maxVal = 0;
        for (int j = 0; j <= n; j++) {
            maxVal = Math.max(maxVal, dp[n][j]);
        }
        
        return maxVal;
    }
}
```
### Algorithm
- Sort the `satisfaction` array in non-decreasing order.
- Create a 2D DP array `dp[n+1][n+1]`.
- The state `dp[i][j]` will represent the maximum like-time coefficient achievable by considering the first `i` dishes from the sorted array and choosing to cook exactly `j` of them.
- Initialize the DP table. The base case is `dp[i][0] = 0` for all `i`, as cooking zero dishes yields a coefficient of 0.
- Iterate through the dishes from `i = 1` to `n` and for each dish, iterate through the number of dishes to cook `j` from `1` to `i`.
- The transition for `dp[i][j]` is `max(dp[i-1][j], dp[i-1][j-1] + satisfaction[i-1] * j)`.
  - `dp[i-1][j]` corresponds to skipping the `i`-th dish.
  - `dp[i-1][j-1] + satisfaction[i-1] * j` corresponds to cooking the `i`-th dish at time `j`.
- The answer is the maximum value in the last row of the DP table, `max(dp[n][j])` for `0 <= j <= n`.

## Iterative Calculation for all Suffixes
A more direct approach is based on the key insight that we should only cook dishes with the highest satisfaction values, and always in increasing order of satisfaction. After sorting the array, the problem reduces to finding which suffix of the sorted array gives the maximum like-time coefficient. This approach iterates through all possible suffixes (by choosing different start points), calculates the sum for each, and finds the maximum.
**Time:** O(n^2). Sorting takes O(n log n). The nested loops to check every suffix take O(n^2) time, making it the dominant factor. · **Space:** O(log n) or O(n), depending on the implementation of the sorting algorithm. The iterative part uses O(1) extra space.
**Pros:** Conceptually simpler than the dynamic programming approach.; Space-efficient, requiring only O(1) extra space besides the storage for sorting.
**Cons:** The O(n^2) time complexity is inefficient for larger inputs.; It recalculates sums repeatedly, whereas a more optimal approach can reuse previous calculations.
### Explanation
The fundamental observation is that to maximize the sum, we should assign larger time multipliers to higher satisfaction values. This implies that if we decide on a set of dishes to cook, we must cook them in increasing order of their satisfaction levels. Therefore, the first step is to sort the `satisfaction` array.

Once sorted, the problem becomes choosing an optimal contiguous suffix of the array to cook. For example, if we decide to cook `k` dishes, we must choose the `k` dishes with the highest satisfaction values, which are the last `k` elements in the sorted array.

This approach directly simulates this. It iterates through every possible starting index `i` from `0` to `n-1` in the sorted array. For each `i`, it considers the subarray `satisfaction[i...n-1]` as the set of dishes to cook. It then calculates the like-time coefficient for this set by iterating from `j = i` to `n-1`, multiplying `satisfaction[j]` by the corresponding time `(j-i+1)`. The maximum sum found across all possible starting indices `i` is the answer. The initial maximum is set to 0 to account for the case where it's best to cook no dishes.

```java
import java.util.Arrays;

class Solution {
    public int maxSatisfaction(int[] satisfaction) {
        Arrays.sort(satisfaction);
        int n = satisfaction.length;
        int maxSatisfaction = 0;

        // i is the starting index of the dishes to cook from the sorted array
        for (int i = 0; i < n; i++) {
            int currentSum = 0;
            int time = 1;
            // Calculate like-time coefficient for subarray satisfaction[i...n-1]
            for (int j = i; j < n; j++) {
                currentSum += satisfaction[j] * time;
                time++;
            }
            maxSatisfaction = Math.max(maxSatisfaction, currentSum);
        }
        
        return maxSatisfaction;
    }
}
```
### Algorithm
- Sort the `satisfaction` array in non-decreasing order.
- Initialize a variable `max_satisfaction` to 0. This will store the final answer and also handles the case where it's optimal to cook no dishes.
- Iterate with an outer loop from `i = 0` to `n-1`. The index `i` represents the starting point of the subarray of dishes we will cook (i.e., `satisfaction[i...n-1]`).
- Inside the loop, for each starting index `i`, calculate the like-time coefficient for that choice of dishes.
  - Initialize `current_sum = 0` and `time = 1`.
  - Start an inner loop from `j = i` to `n-1`.
  - In the inner loop, add `satisfaction[j] * time` to `current_sum` and increment `time`.
- After the inner loop finishes, `current_sum` holds the total coefficient for cooking dishes `satisfaction[i...n-1]`.
- Update `max_satisfaction = max(max_satisfaction, current_sum)`.
- After the outer loop completes, return `max_satisfaction`.

## Greedy Approach with Running Sum
This is the most efficient approach, employing a greedy strategy. After sorting the satisfaction values, we iterate from the dish with the highest satisfaction downwards. We maintain a running sum of the satisfactions of the dishes chosen so far (`suffix_sum`). At each step, we decide whether to include the next most satisfying dish. The change in the total like-time coefficient when adding a new dish can be calculated in O(1) time using the `suffix_sum`, leading to an overall linear time complexity after sorting.
**Time:** O(n log n). The algorithm is dominated by the initial sorting of the array. The subsequent loop runs in O(n) time. · **Space:** O(log n) or O(n) for sorting, depending on the language's implementation. The greedy iteration itself uses O(1) extra space.
**Pros:** Most efficient solution with O(n log n) time complexity, dominated by sorting.; Very space-efficient, using only O(1) extra space (excluding sorting).; The code is concise and elegant.
**Cons:** The greedy logic, while correct, might not be immediately obvious to prove.
### Explanation
This optimal solution builds upon the same initial insight: sort the `satisfaction` array first. Then, we should consider which dishes to include, starting from the one with the highest satisfaction.

Let's iterate from the end of the sorted array. We maintain a `suffix_sum`, which is the sum of satisfactions of the dishes we have included so far. We also maintain the `max_satisfaction` found.

When we consider adding a new dish `satisfaction[i]` (which is the smallest among the currently considered set), it will be cooked at time 1. All other dishes we've already included will have their cooking times shifted up by 1. The increase in the total like-time coefficient from this time shift is exactly the sum of the satisfactions of those other dishes. So, the total change is `satisfaction[i]` (from its own contribution at time 1) plus the sum of all other included dishes. This total change is precisely the new `suffix_sum` (including `satisfaction[i]`).

So, the algorithm is: iterate from `i = n-1` down to `0`. In each step, update `suffix_sum += satisfaction[i]`. If this `suffix_sum` is positive, it means including this dish and all subsequent ones (which we already processed) results in a larger total coefficient. We add this positive `suffix_sum` to our running total `max_satisfaction`. If `suffix_sum` becomes non-positive, we stop. This is because `satisfaction[i]` is decreasing, so `suffix_sum` will only become more negative, and adding it would only decrease the total coefficient. Therefore, we have found the optimal set of dishes.

```java
import java.util.Arrays;

class Solution {
    public int maxSatisfaction(int[] satisfaction) {
        Arrays.sort(satisfaction);
        int n = satisfaction.length;
        int maxSatisfaction = 0;
        int suffixSum = 0; // Sum of satisfactions of dishes we are cooking

        // Iterate from the most satisfying dish to the least
        for (int i = n - 1; i >= 0; i--) {
            // Add the current dish to our consideration
            suffixSum += satisfaction[i];
            
            // If the sum of satisfactions of all chosen dishes is not positive,
            // adding it will not increase the total like-time coefficient.
            // Since we are adding dishes with decreasing satisfaction,
            // the suffixSum will only get smaller from this point.
            // So, we should stop including dishes.
            if (suffixSum <= 0) {
                break;
            }
            
            // When we add a new dish, the total coefficient increases by the
            // sum of satisfactions of all currently chosen dishes.
            maxSatisfaction += suffixSum;
        }
        
        return maxSatisfaction;
    }
}
```
### Algorithm
- Sort the `satisfaction` array in non-decreasing order.
- Initialize `max_satisfaction = 0` and `suffix_sum = 0`.
- Iterate backwards from the end of the sorted array (`i = n-1` down to `0`).
- In each iteration, add the current dish's satisfaction to `suffix_sum`: `suffix_sum += satisfaction[i]`.
- This `suffix_sum` represents the sum of satisfactions of all dishes chosen so far.
- If `suffix_sum` is positive, it means adding this new dish (and all the ones after it) contributes positively to the total coefficient. We add this `suffix_sum` to our `max_satisfaction`.
- If `suffix_sum` becomes zero or negative, any further additions of dishes (with even smaller satisfaction values) will only decrease the total coefficient. Therefore, we can break the loop.
- Return `max_satisfaction`.

# Solutions
### Java

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

```

### CPP

```cpp
class Solution {
public:
  int maxSatisfaction(vector<int> &satisfaction) {
    sort(rbegin(satisfaction), rend(satisfaction));
    int ans = 0, s = 0;
    for (int x : satisfaction) {
      s += x;
      if (s <= 0) {
        break;
      }
      ans += s;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int: satisfaction . sort(reverse=True) ans = s = 0 for x in satisfaction: s += x if s <= 0: break ans += s return ans

```