Problem

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.

Examples

Example 1

1
2
3
4
5

Input: nums = [2,-1,0,1,-3,3,-3]
Output: 6
Explanation: We can rearrange the array into nums = [2,3,1,-1,-3,0,-3].
prefix = [2,5,6,5,2,2,-1], so the score is 6.
It can be shown that 6 is the maximum score we can obtain.

Example 2

1
2
3

Input: nums = [-2,-3,0]
Output: 0
Explanation: Any rearrangement of the array will result in a score of 0.

Constraints

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

Solution

Method 1 – Greedy: Sort Descending and Prefix Sum

Intuition

To maximize the number of positive prefix sums, we should add the largest numbers first. Sorting in descending order ensures the prefix sum stays positive as long as possible.

Approach

  1. Sort the array in descending order.
  2. Iterate through the array, maintaining a running sum.
  3. Count how many times the running sum is positive.
  4. Return the count.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
public:
    int maxScore(vector<int>& nums) {
        sort(nums.rbegin(), nums.rend());
        long long sum = 0;
        int ans = 0;
        for (int x : nums) {
            sum += x;
            if (sum > 0) ++ans;
            else break;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

import "sort"
func maxScore(nums []int) int {
    sort.Slice(nums, func(i, j int) bool { return nums[i] > nums[j] })
    sum, ans := 0, 0
    for _, x := range nums {
        sum += x
        if sum > 0 {
            ans++
        } else {
            break
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

import java.util.*;
class Solution {
    public int maxScore(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length, ans = 0;
        long sum = 0;
        for (int i = n-1; i >= 0; --i) {
            sum += nums[i];
            if (sum > 0) ++ans;
            else break;
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    fun maxScore(nums: IntArray): Int {
        nums.sortDescending()
        var sum = 0L
        var ans = 0
        for (x in nums) {
            sum += x
            if (sum > 0) ans++ else break
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def maxScore(self, nums: list[int]) -> int:
        nums.sort(reverse=True)
        ans = s = 0
        for x in nums:
            s += x
            if s > 0:
                ans += 1
            else:
                break
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

impl Solution {
    pub fn max_score(mut nums: Vec<i32>) -> i32 {
        nums.sort_by(|a, b| b.cmp(a));
        let mut sum = 0i64;
        let mut ans = 0;
        for x in nums {
            sum += x as i64;
            if sum > 0 { ans += 1; } else { break; }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    maxScore(nums: number[]): number {
        nums.sort((a, b) => b - a);
        let ans = 0, sum = 0;
        for (const x of nums) {
            sum += x;
            if (sum > 0) ++ans;
            else break;
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n log n), where n is the length of nums, due to sorting.
  • 🧺 Space complexity: O(1) (or O(n) if sorting is not in-place), as only a few variables are used after sorting.