Reducing Dishes

• 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.

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.

1import java.util.Arrays;2 3class Solution {4    public int maxSatisfaction(int[] satisfaction) {5        int n = satisfaction.length;6        Arrays.sort(satisfaction);7        8        // dp[i][j]: max satisfaction considering first i dishes and cooking j of them9        int[][] dp = new int[n + 1][n + 1];10        // Initialize with a very small value to handle negative satisfactions11        for (int[] row : dp) {12            Arrays.fill(row, Integer.MIN_VALUE / 2); // Avoid overflow on addition13        }14        15        // Base case: cooking 0 dishes gives 0 satisfaction16        for (int i = 0; i <= n; i++) {17            dp[i][0] = 0;18        }19        20        for (int i = 1; i <= n; i++) {21            for (int j = 1; j <= i; j++) {22                // Option 1: Cook the current dish (satisfaction[i-1])23                // This will be the j-th dish cooked.24                int cook = dp[i - 1][j - 1] + satisfaction[i - 1] * j;25                26                // Option 2: Don't cook the current dish27                int skip = dp[i - 1][j];28                29                dp[i][j] = Math.max(cook, skip);30            }31        }32        33        int maxVal = 0;34        for (int j = 0; j <= n; j++) {35            maxVal = Math.max(maxVal, dp[n][j]);36        }37        38        return maxVal;39    }40}

• 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.

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.

1import java.util.Arrays;2 3class Solution {4    public int maxSatisfaction(int[] satisfaction) {5        Arrays.sort(satisfaction);6        int n = satisfaction.length;7        int maxSatisfaction = 0;8 9        // i is the starting index of the dishes to cook from the sorted array10        for (int i = 0; i < n; i++) {11            int currentSum = 0;12            int time = 1;13            // Calculate like-time coefficient for subarray satisfaction[i...n-1]14            for (int j = i; j < n; j++) {15                currentSum += satisfaction[j] * time;16                time++;17            }18            maxSatisfaction = Math.max(maxSatisfaction, currentSum);19        }20        21        return maxSatisfaction;22    }23}

• 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.

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.

1import java.util.Arrays;2 3class Solution {4    public int maxSatisfaction(int[] satisfaction) {5        Arrays.sort(satisfaction);6        int n = satisfaction.length;7        int maxSatisfaction = 0;8        int suffixSum = 0; // Sum of satisfactions of dishes we are cooking9 10        // Iterate from the most satisfying dish to the least11        for (int i = n - 1; i >= 0; i--) {12            // Add the current dish to our consideration13            suffixSum += satisfaction[i];14            15            // If the sum of satisfactions of all chosen dishes is not positive,16            // adding it will not increase the total like-time coefficient.17            // Since we are adding dishes with decreasing satisfaction,18            // the suffixSum will only get smaller from this point.19            // So, we should stop including dishes.20            if (suffixSum <= 0) {21                break;22            }23            24            // When we add a new dish, the total coefficient increases by the25            // sum of satisfactions of all currently chosen dishes.26            maxSatisfaction += suffixSum;27        }28        29        return maxSatisfaction;30    }31}