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)));
    }
};

• Java
• C++
• Python
• Go

• 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
  }
  

All Problems

All Solutions