Hard
,Array
,DP
,Greedy
,Sorting
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 do not like the dishes. No dish is prepared.
Constraints:
days.length
<= 365days[i]
<= 365days
is in strictly increasing order.costs.length
== 3costs[i]
<= 1000作法: Greedy,先對菜餚做排序,價值越高的菜餚要累加越多次,直到當前滿意度 < 0 時,則停止計算
class Solution:
def maxSatisfaction(self, satisfaction: List[int]) -> int:
satisfaction = sorted(satisfaction)
suffix_sum, max_satisfaction = 0, 0
for i in range(len(satisfaction) - 1, -1, -1):
if suffix_sum + satisfaction[i] > 0:
suffix_sum += satisfaction[i]
max_satisfaction += suffix_sum
return max_satisfaction
Ron ChenWed, Mar 29, 2023
class Solution:
def maxSatisfaction(self, satisfaction: List[int]) -> int:
satisfaction.sort(reverse=True)
total, ans = 0, 0
for value in satisfaction:
if total + value <= 0: break
total += value
ans += total
return ans
Yen-Chi ChenWed, Mar 29, 2023
class Solution:
def maxSatisfaction(self, satisfaction: List[int]) -> int:
satisfaction.sort(reverse=True)
if satisfaction[0] <= 0:
return 0
total = 0
max_value = 0
for i, _ in enumerate(satisfaction):
total = sum([(i-j+1)*satisfaction[j] for j in range(i+1)])
if total > max_value:
max_value = total
return max_value
gpwork4uThur, Mar 30, 2023
class Solution {
public:
int maxSatisfaction(vector<int>& satisfaction) {
sort(satisfaction.begin(), satisfaction.end(), greater<int>());
int sum = 0, ans = 0;
for (auto value : satisfaction) {
sum += value;
if (sum <= 0) break;
ans += sum;
}
return ans;
}
};
Yen-Chi ChenWed, Mar 29, 2023
function maxSatisfaction(satisfaction) {
satisfaction.sort((a, b) => b - a);
let max = 0;
let sum = 0;
for (const num of satisfaction) {
sum += num;
if (sum > 0) {
max += sum;
} else {
break;
}
}
return max;
}
MarsgoatWed, Mar 29, 2023