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

链接：2587.重排数组以得到最大前缀分数
难度：Medium
标签：贪心、数组、前缀和、排序
简介：给你一个下标从 0 开始的整数数组 nums 。你可以将 nums 中的元素按 任意顺序 重排（包括给定顺序）。返回可以得到的最大分数。

题解 1 - cpp

• 编辑时间：2023-03-12
• 执行用时：132ms
• 内存消耗：81MB
• 编程语言：cpp
• 解法介绍：贪心从正到负依次取值。

class Solution {
public:
    int maxScore(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        long long n = nums.size(), sum = 0, res = 0;
        if (nums[n - 1] <= 0) return 0;
        for (int i = n - 1; i >= 0; i--) {
            sum += nums[i];
            if (sum <= 0) break;
            res++;
        }
        return res;
    }
};

题解 2 - python

• 编辑时间：2023-03-12
• 执行用时：164ms
• 内存消耗：28.8MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def maxScore(self, nums: List[int]) -> int:
        nums.sort()
        n, sums, res = len(nums), 0, 0
        if nums[n-1] <= 0:
            return 0
        for i in range(n-1, -1, -1):
            sums += nums[i]
            if sums <= 0:
                break
            res += 1
        return res

题解 3 - rust

• 编辑时间：2023-03-12
• 执行用时：32ms
• 内存消耗：3.4MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn max_score(nums: Vec<i32>) -> i32 {
        let mut nums = nums;
        nums.sort();
        let (n, mut sum, mut res) = (nums.len(), 0i64, 0);
        if *nums.last().unwrap() <= 0 {
            0
        } else {
            for i in (0..n).rev() {
                sum += nums[i] as i64;
                if sum <= 0 {
                    break;
                }
                res += 1;
            }
            res
        }
    }
}