难度: Medium
给你一个下标从 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运行时间: 118 ms
内存: 29.6 MB
class Solution:
def maxScore(self, nums: List[int]) -> int:
count1 = count2 = 0
negs = []
res = 0
for num in nums:
if num > 0:
count1 += num
res += 1
else:
# idx = bisect.bisect(negs, -num)
# negs.insert(idx, -num)
negs.append(-num)
negs.sort()
for neg in negs:
count1 -= neg
res += (count1 > 0)
return res
此题目的核心思想是通过尽可能保持前缀和为正数来最大化数组的分数。首先，遍历数组，将正数累加到一个计数器中，并直接计算这些正数对分数的贡献。负数和零被存储在一个列表中用于后续处理。将负数列表进行排序后，从最小的负数开始逐个从前缀和中扣除，每次扣除后检查前缀和是否仍为正数，如果是，则分数加一。这样，通过优先扣除小的负数，可以尽量保持前缀和的正性，从而增加分数。
时间复杂度: O(n log n)
空间复杂度: O(n)
class Solution:
def maxScore(self, nums: List[int]) -> int:
count1 = count2 = 0 # count1用于累计正数和，count2未使用
negs = [] # 存储负数的列表
res = 0 # 初始化分数为0
for num in nums:
if num > 0:
count1 += num # 累加正数
res += 1 # 正数直接增加分数
else:
# 存储负数，用于后续处理
negs.append(-num)
negs.sort() # 对负数进行排序
for neg in negs:
count1 -= neg # 从当前总和中减去负数
res += (count1 > 0) # 如果当前总和仍然是正数，分数加一
return res
在初次遍历时，我们优先处理正数是为了尽可能保持前缀和的正数状态，从而最大化前缀分数。如果在初次遍历时就处理负数和0，会立即影响前缀和的值，可能导致前缀和过早变为负数，从而减少可获得的分数。通过将负数和0暂时存储起来，我们可以在后续有更多控制地调整前缀和，比如通过有选择地添加一些较小的负值，从而尽可能地保持前缀和为正数，以提高总体得分。
对负数进行排序是为了确保我们首先处理绝对值最小的负数（即对前缀和影响最小的负数）。这种策略使我们可以在尽可能保持前缀和为正的同时，逐步处理每个负数。如果不排序而是随机处理负数，可能会导致前缀和过早地变成负数，从而减少得到正前缀和的次数，影响总分。通过从小到大处理负数，我们最大化了保持前缀和为正值的机会，从而最大化分数。
代码中的`count2`变量没有在后续的逻辑中被使用，这可能是代码编写过程中的一个错误或遗漏。通常这种未使用的变量可以被视为冗余，除非原始设计中有特定的功能计划，但未实现。没有具体的上下文说明其用途，看起来像是应该从代码中移除的无用变量。
表达式`(count1 > 0)`的返回值是一个布尔值，其中`True`代表`count1`是正数，`False`代表不是。在Python中，布尔值`True`和`False`分别可以被当作整数`1`和`0`进行数学运算。因此，在每次从前缀和中减去一个负数后，如果前缀和仍然是正的，则`(count1 > 0)`会返回`True`，相当于向`res`中添加`1`；如果结果是负的，则返回`False`，相当于向`res`中添加`0`。这样的逻辑确保只有当前缀和为正时，分数`res`才增加。