2587. Rearrange Array to Maximize Prefix Score
Description
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.
Example 1:
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:
Input: nums = [-2,-3,0] Output: 0 Explanation: Any rearrangement of the array will result in a score of 0.
Constraints:
1 <= nums.length <= 105
-106 <= nums[i] <= 106
Solutions
Solution 1: Greedy + Sorting
To maximize the number of positive integers in the prefix sum array, we need to make the elements in the prefix sum array as large as possible, that is, to add as many positive integers as possible. Therefore, we can sort the array $nums$ in descending order, then traverse the array, maintaining the prefix sum $s$. If $s \leq 0$, it means that there can be no more positive integers in the current position and the positions after it, so we can directly return the current position.
Otherwise, after the traversal, we return the length of the array.
The time complexity is $O(n \times \log n)$, and the space complexity is $O(\log n)$. Here, $n$ is the length of the array $nums$.
1 2 3 4 5 6 7 8 9 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|