Best Order for a Tasting Menu

Hard

A chef is putting together a tasting menu. Each dish has a taste score tastes[i], which may be negative. Dishes are served one at a time, and the dish served t-th (counting from one) earns t · tastes[i] points. The chef may pick any subset of dishes, including none, and serve them in any order. Return the largest total score possible.

Example 1

tastes=[-2, 6, -7, 1] → 18

Serve -2, 1, 6 in that order: -2·1 + 1·2 + 6·3 = 18. The -7 dish is better left out.

Example 2

tastes=[3, 5, 1] → 22

All dishes in increasing order: 1·1 + 3·2 + 5·3 = 22.

Example 3

tastes=[-4, -1] → 0

Any menu gives a negative total, so it is best to cook nothing: 0.

Constraints

1 ≤ len(tastes) ≤ 10⁵
-1000 ≤ tastes[i] ≤ 1000

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Array Dynamic Programming Sorting

Similar problems

Biggest Number Divisible by Three Hard Edge Toggles on a Tree Hard Fewest Meetings to Cancel Medium Longest Chain of Segments Medium A Haul That Splits Three Ways Medium

Input

tastes=[-2, 6, -7, 1]

Expected

Run checks the first 3 tests in your browser. Submit checks all 116 tests on the server, hidden ones included.