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

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

Code

[{"language":"C++","code":"class Solution {\npublic:\n    int maxScore(vector<int>& nums) {\n        sort(nums.rbegin(), nums.rend());\n        long long sum = 0;\n        int ans = 0;\n        for (int x : nums) {\n            sum += x;\n            if (sum > 0) ++ans;\n            else break;\n        }\n        return ans;\n    }\n};","lang":"cpp","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">class</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> Solution</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">public:</span></span>\n<span class=\"line\"><span style=\"col

Related Tags