2587-重排数组以得到最大前缀分数

给你一个下标从 0 开始的整数数组 nums 。你可以将 nums 中的元素按 任意顺序 重排（包括给定顺序）。

令 prefix 为一个数组，它包含了 nums 重新排列后的前缀和。换句话说，prefix[i] 是 nums 重新排列后下标从 0
到 i 的元素之和。nums 的 分数 是 prefix 数组中正整数的个数。

返回可以得到的最大分数。

示例 1：

**输入：** nums = [2,-1,0,1,-3,3,-3]
**输出：** 6
**解释：** 数组重排为 nums = [2,3,1,-1,-3,0,-3] 。
prefix = [2,5,6,5,2,2,-1] ，分数为 6 。
可以证明 6 是能够得到的最大分数。

示例 2：

**输入：** nums = [-2,-3,0]
**输出：** 0
**解释：** 不管怎么重排数组得到的分数都是 0 。

提示：

• 1 <= nums.length <= 105
• -106 <= nums[i] <= 106

下午两点【biIibiIi@灵茶山艾府】直播讲题，记得关注哦~

---

对于一个负数来说，它后面的前缀和都会把这个负数加进去。

由于要统计的是正数前缀和，那么把负数尽量放在后面，能统计到尽量多的正数前缀和。

同时，绝对值小的负数应该排在负数的前面，尽量在前缀和减为负数前还能多统计一些正数。

[sol1-Python3]

class Solution:
    def maxScore(self, nums: List[int]) -> int:
        nums.sort(reverse=True)
        return sum(s > 0 for s in accumulate(nums))

[sol1-Go]

func maxScore(nums []int) (ans int) {
	sort.Sort(sort.Reverse(sort.IntSlice(nums)))
	sum := 0
	for _, x := range nums {
		sum += x
		if sum <= 0 {
			break
		}
		ans++
	}
	return
}

复杂度分析

• 时间复杂度：O(n\log n)，其中 n 为 nums 的长度。
• 空间复杂度：O(1)。忽略排序时的栈开销，仅用到若干额外变量。