Rearrange array to maximize prefix score

Array Greedy Sorting Prefix Sum

42.5% acceptance

Feb 25, 2026

309

You are given a 0-indexed integer array nums. You can rearrange the elements of nums to any order (including the given order). Let prefix be the array containing the prefix sums of nums after rearranging it. In other words, prefix[i] is the sum of the elements from 0 to i in nums after rearranging it. The score of nums is the number of positive integers in the array prefix. Return the maximum score you can achieve.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn max_score(mut nums: Vec<i32>) -> i32 {
    // You are given a 0-indexed integer array nums. You can rearrange the elements
    // of nums to any order. Let prefix be the array containing the prefix sums of nums
    // after rearranging it. The score of nums is the number of positive integers in prefix.
    // Return the maximum score you can achieve.
    // Strategy: sort descending so we keep prefix sums positive as long as possible.
    nums.sort_unstable_by(|a, b| b.cmp(a));
    let mut sum = 0i64;
    let mut score = 0;
    for x in nums {
      sum += x as i64;
      if sum > 0 {
        score += 1;
      } else {
        break;
      }
    }
    score
  }
}