Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1402.html
1402. Reducing Dishes (Hard)
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
Related Topics:
Dynamic Programming
Solution 1. Brute Force
// OJ: https://leetcode.com/problems/reducing-dishes/
// Time: O(N^2)
// Space: O(1)
class Solution {
typedef long long LL;
public:
int maxSatisfaction(vector<int>& A) {
int N = A.size();
sort(A.begin(), A.end());
LL ans = 0;
for (int i = 0; i < N; ++i) {
LL sum = 0;
for (int j = i; j < N; ++j) sum += A[j] * (j - i + 1);
ans = max(ans, sum);
}
return ans;
}
};
Solution 2. Prefix Sum
If array is sorted in descending order. The answer is one of the following:
- B[0] = A[0] * 1
- B[1] = A[0] * 2 + A[1] * 1
- B[2] = A[0] * 3 + A[1] * 2 + A[2] * 1
- …
And we have
- B[0] = Sum(0)
- B[1] = B[0] + Sum(1)
- B[2] = B[1] + Sum(2)
- …
Where Sum(i) = A[0] + ... + A[i]
, i.e. prefix sum of A
.
- B[0] = Sum(0)
- B[1] = Sum(0) + Sum(1)
- B[2] = Sum(0) + Sum(1) + Sum(2)
- …
And thus B
is the prefix sum of prefix sum of A
.
// OJ: https://leetcode.com/problems/reducing-dishes/
// Time: O(NlogN)
// Space: O(1)
class Solution {
public:
int maxSatisfaction(vector<int>& A) {
sort(begin(A), end(A), greater<int>());
partial_sum(begin(A), end(A), begin(A));
partial_sum(begin(A), end(A), begin(A));
return max(0, *max_element(begin(A), end(A)));
}
};
-
class Solution { public int maxSatisfaction(int[] satisfaction) { Arrays.sort(satisfaction); int startIndex = -1; int length = satisfaction.length; for (int i = 0; i < length; i++) { if (satisfaction[i] >= 0) { startIndex = i; break; } } if (startIndex < 0) return 0; int sum = 0; int totalSatisfaction = 0; int time = 1; for (int i = startIndex, j = 1; i < length; i++, j++) { sum += satisfaction[i]; totalSatisfaction += satisfaction[i] * j; } int maxSatisfaction = totalSatisfaction; for (int i = startIndex - 1; i >= 0; i--) { sum += satisfaction[i]; if (sum < 0) break; totalSatisfaction += sum; maxSatisfaction = Math.max(maxSatisfaction, totalSatisfaction); } return maxSatisfaction; } } ############ class Solution { public int maxSatisfaction(int[] satisfaction) { Arrays.sort(satisfaction); int ans = 0, presum = 0; for (int i = satisfaction.length - 1; i >= 0; --i) { presum += satisfaction[i]; if (presum > 0) { ans += presum; } else { break; } } return ans; } }
-
// OJ: https://leetcode.com/problems/reducing-dishes/ // Time: O(N^2) // Space: O(1) class Solution { typedef long long LL; public: int maxSatisfaction(vector<int>& A) { int N = A.size(); sort(A.begin(), A.end()); LL ans = 0; for (int i = 0; i < N; ++i) { LL sum = 0; for (int j = i; j < N; ++j) sum += A[j] * (j - i + 1); ans = max(ans, sum); } return ans; } };
-
class Solution: def maxSatisfaction(self, satisfaction: List[int]) -> int: satisfaction.sort(reverse=True) ans = presum = 0 for v in satisfaction: presum += v if presum > 0: ans += presum else: break return ans
-
func maxSatisfaction(satisfaction []int) int { sort.Ints(satisfaction) ans, presum := 0, 0 for i := len(satisfaction) - 1; i >= 0; i-- { presum += satisfaction[i] if presum > 0 { ans += presum } else { break } } return ans }