Sponsored
Sponsored
To maximize the like-time coefficient, we can sort the satisfaction levels in non-descending order and calculate the possible like-time coefficients by considering prefixes from the end of the sorted array. This allows us to selectively choose higher satisfaction dishes to maximize the total like-time coefficient.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) for using a constant amount of extra space.
1function maxSatisfaction(satisfaction) {
2 satisfaction.sort((a, b) => a - b);
3 let total = 0, prefixSum = 0;
4 for (let i = satisfaction.length - 1; i >= 0; i--) {
5 prefixSum += satisfaction[i];
6 if (prefixSum > 0) {
7 total += prefixSum;
8 } else {
9 break;
10 }
11 }
12 return total;
13}
14
15const satisfaction = [-1, -8, 0, 5, -9];
16console.log(maxSatisfaction(satisfaction));This JavaScript function sorts the array and calculates the total like-time coefficient from the back, selecting positive prefix sums only.
An alternative approach involves using dynamic programming to maximize the like-time coefficient. We maintain a DP table where `dp[i]` represents the maximum like-time coefficient attainable using the first `i` dishes. This approach computes overlap coefficients dynamically using state transitions calculated for each dish considered.
Time Complexity: O(n^2)
Space Complexity: O(n)
1
This C solution employs dynamic programming by initializing a DP array with zero and iteratively updating it by considering the choice of including a dish or not, thereby maximizing the like-time coefficient.