Show problems as
Classic problem #1402HardArrayDynamic ProgrammingGreedySorting

Reducing Dishes

Real-world version: Running Order For The Demo Reel
Tracked in this browser only
Read Reducing Dishes on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A showcase reel is cut together from a pile of clips. Clip i has been given a rating ratings[i] by the review panel, and a rating may be negative when the panel disliked the clip.

You choose which clips go into the reel and what order they play in. Any number of clips may be left out, including all of them. A clip that ends up in position p of the finished reel scores p * rating, where positions are numbered 1, 2, 3, ... over the clips that were actually included, so leaving a clip out shifts everything after it one position earlier. The reel's value is the sum of the scores of its clips, and an empty reel is worth 0.

Return the largest value a reel cut from these clips can have.

Examples

Example 1

Input
ratings = [-4, 1, 2]
Output
5

Leave the clip rated -4 out and play the other two as 1 then 2. That reel scores 1 * 1 + 2 * 2 = 5.

Example 2

Input
ratings = [-1, 5, 6]
Output
27

Include all three clips in the order -1, 5, 6. The scores are 1 * (-1), 2 * 5 and 3 * 6, which add up to 27.

Example 3

Input
ratings = [-7, -2, -3]
Output
0

Every clip is rated below zero. Leaving all of them out gives an empty reel, worth 0.

Constraints

  • n == ratings.length
  • 1 <= n <= 500
  • -1000 <= ratings[i] <= 1000

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def max_reel_value(ratings: list[int]) -> int:
Java
public int maxReelValue(int[] ratings)

More on the same topics