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.
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5int maxSatisfaction(std::vector<int>& satisfaction) {
6 std::sort(satisfaction.begin(), satisfaction.end(), std::greater<int>());
7 int total = 0, sum = 0;
8 for (int s : satisfaction) {
9 sum += s;
10 if (sum > 0) {
11 total += sum;
12 } else {
13 break;
14 }
15 }
16 return total;
17}
18
19int main() {
20 std::vector<int> satisfaction = {-1, -8, 0, 5, -9};
21 std::cout << maxSatisfaction(satisfaction);
22 return 0;
23}This C++ solution similarly sorts the satisfaction levels in decreasing order. It then iteratively accumulates the like-time coefficient, stopping when the running sum becomes non-positive.
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 JavaScript approach uses dynamic programming. An array tracks maximum scores achievable and updates state based on including or excluding dishes from past planned courses.