LeetCode: Problem #1402. Reducing Dishes

Problem Statement:

A chef has collected the data on the review for his dishes. Our Chef will take just 1 unit of time to prepare a dish.

Our job is to tell him the dishes he has to make in the order to achieve maximum benefit. The maximum benefit is calculated using the formula time[i] * (review ratings).

Example 1:

Input:

reviews = [-1, -10, -9, 0, 5]

Output:14

Explanation:

Considering the dishes in the order of -1, 0 ,5 the calculation will be (-1 * 1 + 0 * 2 + 5 * 3) = 14

Example 2:

Input:

reviews = [6,5,4]

Output:32

Explanation:

Considering the dishes in the order of 4, 5, 6 the calculation will be (4 * 1 + 5 * 2 + 6 * 3) = 32

Approach to the solution:

1. Sort the given reviews so that we can concentrate only on maximum benefited reviews.
2. Make cumulative sums from the end.
3. This will help in deciding till which we have to consider the summation.
4. Now start from the end at add the previous array of cumulative sums until a negative number is encountered.
5. We have to iterate in reverse order till negative number is encountered because it will decide whether adding those dish will benefit or not.

Solution in C++:

class Solution {
public:
    int maxSatisfaction(vector<int>& satisfaction) {        
        //sorting vector
        sort(satisfaction.begin(), satisfaction.end());        
        vector<int> sums(satisfaction);
            int temp = 0;
        if(sums.back() <= 0)
            return 0;
        for(auto iter = sums.rbegin(); iter != sums.rend(); ++iter){
            *iter = temp + *iter;
            temp = *iter;
        }
        int max_sum = INT_MIN;
        temp = 0;
        for(auto iter = sums.rbegin(); iter != sums.rend(); ++iter){
            if(*iter < 0)
                return max_sum;
            temp += *iter;
            max_sum = max(max_sum, temp);
        }
        return max_sum;
    }
};