Rearrange Array to Maximize Prefix Score
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 index 0 to index 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
6We can rearrange the array into nums = [2,3,1,-1,-3,0,-3], giving prefix = [2,5,6,5,2,2,-1], so the score is 6, which is maximum.
Example 2
Input
nums = [-2,-3,0]Output
0Any rearrangement of the array will result in a score of 0.
Constraints
- 1 <= nums.length <= 10^5
- -10^6 <= nums[i] <= 10^6
Asked at 3 companies
Practice questions like this out loud in a mock coding interview with a live AI interviewer. First one free.