Rearrange Array to Maximize Prefix Score

Challenge Points: 20

Level: Medium

You are given an integer array nums. You are allowed to reorder its elements in any way you want.

After rearranging the array, we compute a prefix sum array, where:

prefix[i] = sum of elements from index 0 to i in the reordered array.

Your task is to maximize the score, which is defined as:

The number of prefix sums that are strictly positive.

Return the highest possible score obtainable by optimally rearranging the array.

Example 1:

Input: nums = [5, -2, -1, 4, -3]

Output: 5

Explanation:

One optimal order is: [5, 4, -1, -2, -3] Prefix sums: [5, 9, 8, 6, 3] → all positive → score = 5 But since one element can be placed differently, best guaranteed score = 4.

Example 2:

Input: nums = [-5, -2, -1]

Output: 0

Explanation:

All numbers are negative, so no rearrangement can produce a positive prefix sum.

to Continue

Accepted:

Submission:

Report an issue

Code

You need toto run or submitYou need toto run or submit

Test Case

Test Result