Show problems as
Classic problem #2587MediumArrayGreedySortingPrefix Sum

Rearrange Array to Maximize Prefix Score

Real-world version: Ordering Entries to Keep the Totals Above Zero
Tracked in this browser only
Read Rearrange Array to Maximize Prefix Score on LeetCode(opens in a new tab)

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

A list entries holds whole numbers, and they may be arranged in any order at all.

Once arranged, form the running totals: the first entry, then the first two added together, then the first three, and so on, giving one total per entry.

Return the largest number of those running totals that can be strictly above zero.

Examples

Example 1

Input
entries = [-6, -5, 4, 3, 2, 1]
Output
5

Taking the four positive entries first gives totals of 4, 7, 9 and 10. Adding -5 leaves 5, still above zero, and adding -6 drops it to -1, so five totals stay above zero.

Example 2

Input
entries = [5, -5, 5, -5]
Output
3

The two entries of 5 first give 5 and then 10, one -5 leaves 5, and the last brings the total exactly to zero, which does not count.

Example 3

Input
entries = [-1, -2, -3]
Output
0

Every entry is below zero, so whatever the order the very first total is already negative.

Constraints

  • 1 <= entries.length <= 10^5
  • -10^6 <= entries[i] <= 10^6

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_score(entries: list[int]) -> int:
Java
public int maxScore(int[] entries)

More on the same topics