Hard

Quiz

#1402 Reducing Dishes

APPROACH

A chef has n dishes with satisfaction levels given by the satisfaction array. Each dish takes one time unit. The like-time coefficient of a dish cooked at time slot t (1-indexed) is t * satisfaction. The chef may select any subset of dishes, cooked in any order, to maximize the total like-time coefficient. Return 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.

1 of 4

1:00

What is the optimal approach for this problem?