class Solution {
public:
int maxSatisfaction(vector<int>& satisfaction) {
}
};
1402. 做菜顺序
一个厨师收集了他 n 道菜的满意程度 satisfaction ，这个厨师做出每道菜的时间都是 1 单位时间。
一道菜的 「喜爱时间」系数定义为烹饪这道菜以及之前每道菜所花费的时间乘以这道菜的满意程度，也就是 time[i]*satisfaction[i] 。
请你返回做完所有菜 「喜爱时间」总和的最大值为多少。
你可以按 任意 顺序安排做菜的顺序，你也可以选择放弃做某些菜来获得更大的总和。
示例 1：
输入：satisfaction = [-1,-8,0,5,-9] 输出：14 解释：去掉第二道和最后一道菜，最大的喜爱时间系数和为 (-1*1 + 0*2 + 5*3 = 14) 。每道菜都需要花费 1 单位时间完成。
示例 2：
输入：satisfaction = [4,3,2] 输出：20 解释：按照原来顺序相反的时间做菜 (2*1 + 3*2 + 4*3 = 20)
示例 3：
输入：satisfaction = [-1,-4,-5] 输出：0 解释：大家都不喜欢这些菜，所以不做任何菜可以获得最大的喜爱时间系数。
提示：
n == satisfaction.length1 <= n <= 500-1000 <= satisfaction[i] <= 1000原站题解
golang 解法, 执行用时: 0 ms, 内存消耗: 2.2 MB, 提交时间: 2023-10-22 00:02:54
func maxSatisfaction1(satisfaction []int) int {
n := len(satisfaction)
dp := make([][]int, n + 1)
for i := 0; i <= n; i++ {
dp[i] = make([]int, n + 1)
}
sort.Ints(satisfaction)
res := 0
for i := 1; i <= n; i++ {
for j := 1; j <= i; j++ {
dp[i][j] = dp[i - 1][j - 1] + satisfaction[i - 1] * j
if j < i {
dp[i][j] = max(dp[i][j], dp[i - 1][j])
}
res = max(res, dp[i][j])
}
}
return res
}
func max(x, y int) int {
if x < y {
return y
}
return x
}
func maxSatisfaction(satisfaction []int) int {
sort.Slice(satisfaction, func(i, j int) bool {
return satisfaction[i] > satisfaction[j]
})
presum, ans := 0, 0
for _, si := range satisfaction {
if presum + si > 0 {
presum += si
ans += presum
} else {
break
}
}
return ans
}
java 解法, 执行用时: 11 ms, 内存消耗: 42.7 MB, 提交时间: 2023-10-22 00:02:29
class Solution {
public int maxSatisfaction(int[] satisfaction) {
int n = satisfaction.length;
int[][] dp = new int[n + 1][n + 1];
Arrays.sort(satisfaction);
int res = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
dp[i][j] = dp[i - 1][j - 1] + satisfaction[i - 1] * j;
if (j < i) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j]);
}
res = Math.max(res, dp[i][j]);
}
}
return res;
}
public int maxSatisfaction2(int[] satisfaction) {
Arrays.sort(satisfaction);
for (int i = 0, j = satisfaction.length - 1; i < j; i++, j--) {
int temp = satisfaction[i];
satisfaction[i] = satisfaction[j];
satisfaction[j] = temp;
}
int presum = 0, ans = 0;
for (int si : satisfaction) {
if (presum + si > 0) {
presum += si;
ans += presum;
} else {
break;
}
}
return ans;
}
}
cpp 解法, 执行用时: 12 ms, 内存消耗: 7.9 MB, 提交时间: 2023-03-21 10:21:31
class Solution {
public:
int maxSatisfaction(vector<int>& satisfaction) {
sort(satisfaction.begin(), satisfaction.end());
int size=satisfaction.size();
if (satisfaction[size-1]<=0)
return 0;
vector<int> dp(size, 0);
dp[size-1]=satisfaction[size-1];
for (int i=size-2;i>=0;i--) {
int temp=0;
for (int j=size-1;j>=i;j--) {
temp+=satisfaction[j];
}
dp[i]=max(dp[i+1], dp[i+1]+temp);
}
return dp[0];
}
};
python3 解法, 执行用时: 44 ms, 内存消耗: 15 MB, 提交时间: 2023-03-21 10:21:08
class Solution:
def maxSatisfaction(self, satisfaction: List[int]) -> int:
satisfaction.sort()
# print(satisfaction)
# 用贪心算法，获取最大收益即可
res = total = 0
while satisfaction and satisfaction[-1] + total > 0:
total += satisfaction.pop()
res += total
return res
python3 解法, 执行用时: 32 ms, 内存消耗: 14.8 MB, 提交时间: 2023-03-21 10:20:26
class Solution:
def maxSatisfaction(self, satisfaction: List[int]) -> int:
satisfaction.sort(reverse=True)
ans = pre = 0
for num in satisfaction:
pre += num
if pre >= 0:
ans += pre
else:
break
return ans
python3 解法, 执行用时: 28 ms, 内存消耗: 15.1 MB, 提交时间: 2023-03-21 10:20:12
class Solution:
def maxSatisfaction(self, satisfaction: List[int]) -> int:
# 排序
satisfaction.sort()
n = len(satisfaction)
post = 0
start = n
# 从大到小遍历
for i in range(n - 1, -1, -1):
post += satisfaction[i]
if post <= 0:
break
start = i
if start == n:
return 0
return sum(satisfaction[j] * (j - start + 1) for j in range(start, n))