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 dishes preparation.
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 don't like the dishes. No dish is prepared.
Example 4:
Input: satisfaction = [-2,5,-1,0,3,-3] Output: 35
Constraints:
n == satisfaction.length
1 <= n <= 500
-10^3 <= satisfaction[i] <= 10^3
Solution 1: Sort + Brute Force
Time complexity: O(nlogn + n^2)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
// Author: Huahua class Solution { public: int maxSatisfaction(vector<int>& s) { const int n = s.size(); sort(begin(s), end(s)); int ans = 0; for (int i = 0; i < n; ++i) { int v = 0; for (int j = i; j < n; ++j) v += s[j] * (j - i + 1); ans = max(ans, v); } return ans; } }; |
Solution 2: Sort + prefix sum
Sort in reverse order, accumulate prefix sum until prefix sum <= 0.
Time complexity: O(nlogn + n)
Space complexity: O(1)
[9, 8, 5, 2, 1, -1]
sum = 9 * 4 + 8 * 3 + 2 * 3 + 1 * 2 + -1 * 1
<=>
sum += 9
sum += (9 + 8 = 17)
sum += (17 + 2 = 19)
sum += (19 + 1 = 20)
sum += (20 – 1 = 19)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
// Author: Huahua class Solution { public: int maxSatisfaction(vector<int>& s) { const int n = s.size(); sort(rbegin(s), rend(s)); int ans = 0; int prefix = 0; for (int v : s) { prefix += v; if (prefix <= 0) break; ans += prefix; } return ans; } }; |