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.
1def max_satisfaction(satisfaction):
2 satisfaction.sort()
3 total = 0
4 prefix_sum = 0
5 for s in reversed(satisfaction):
6 prefix_sum += s
7 if prefix_sum > 0:
8 total += prefix_sum
9 else:
10 break
11 return total
12
13satisfaction = [-1, -8, 0, 5, -9]
14print(max_satisfaction(satisfaction))In Python, the satisfaction list is sorted, and the like-time coefficient is computed with a running prefix sum, which lets us selectively include positive contributions.
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#include <vector>
#include <algorithm>
int maxSatisfaction(std::vector<int>& satisfaction) {
std::sort(satisfaction.begin(), satisfaction.end());
int n = satisfaction.size();
std::vector<int> dp(n + 1, 0);
for (int i = n - 1; i >= 0; i--) {
for (int t = 0; t <= i; t++) {
dp[t] = std::max(dp[t], dp[t + 1] + satisfaction[i] * (t + 1));
}
}
return dp[0];
}
int main() {
std::vector<int> satisfaction = {4, 3, 2};
std::cout << maxSatisfaction(satisfaction);
return 0;
}This C++ version applies dynamic programming to update the DP array by comparing the inclusion and exclusion of each dish, computing the optimal like-time coefficient.