3974. K 个元素的最大总和

题目描述

给你一个整数数组 nums，以及两个整数 k 和 mul。

从 nums 中选出恰好 k 个元素。你可以按照任意顺序逐个处理这些元素。

对于每个被选择的元素，都可以 独立地 选择以下两种操作之一：

将该元素的值加到总和中；或
将该元素乘以 mul 的当前值，并将结果加到总和中。

每处理一个被选择的元素后，无论选择哪种操作，mul 都会减少 1。mul 的当前值可能变为 0 或负数。

返回一个整数，表示可能得到的最大总和。

示例 1：

输入： nums = [6,1,2,9], k = 3, mul = 2

输出： 26

解释：

一种最优方式如下：

一种最优选择是 nums[3] = 9、nums[0] = 6 和 nums[2] = 2。
先处理 nums[3] = 9：选择乘法，因此贡献 9 * 2 = 18。此时，mul 变为 1。
接着处理 nums[0] = 6：选择乘法，因此贡献 6 * 1 = 6。此时，mul 变为 0。
最后处理 nums[2] = 2：选择直接相加，因此贡献 2。
总和为 18 + 6 + 2 = 26。

示例 2：

输入： nums = [3,7,5,2], k = 2, mul = 4

输出： 43

解释：

一种最优方式如下：

一种最优选择是 nums[1] = 7 和 nums[2] = 5。
先处理 nums[1] = 7：选择乘法，因此贡献 7 * 4 = 28。此时，mul 变为 3。
接着处理 nums[2] = 5：选择乘法，因此贡献 5 * 3 = 15。
总和为 28 + 15 = 43。

示例 3：

输入： nums = [4,4], k = 1, mul = 1

输出： 4

解释：

一种最优方式如下：

一种最优选择是 nums[0] = 4。
处理 nums[0] = 4：选择乘法，因此贡献 4 * 1 = 4。
总和为 4。

提示：

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁵
1 <= k <= nums.length
1 <= mul <= 10⁵

解法

方法一：贪心 + 排序

我们不妨对数组 \(\textit{nums}\) 排序，然后从大到小依次选择 \(k\) 个元素。对于当前第 \(i\) 个元素，我们可以选择将其乘以 \(\max(1, \textit{mul})\) 并加到总和中，然后 \(\textit{mul}\) 减 \(1\)。最后返回总和即可。

时间复杂度 \(O(n \log n)\)，空间复杂度 \(O(\log n)\)。其中 \(n\) 是数组 \(\textit{nums}\) 的长度。

Python3JavaC++GoTypeScript

class Solution:
    def maxSum(self, nums: list[int], k: int, mul: int) -> int:
        nums.sort()
        n = len(nums)
        ans = 0
        for i in range(n - 1, n - 1 - k, -1):
            ans += nums[i] * max(1, mul)
            mul -= 1
        return ans

class Solution {
    public long maxSum(int[] nums, int k, int mul) {
        Arrays.sort(nums);
        int n = nums.length;
        long ans = 0;

        for (int i = n - 1; i >= n - k; i--) {
            int m = Math.max(1, mul);
            ans += (long) nums[i] * m;
            mul--;
        }

        return ans;
    }
}

class Solution {
public:
    long long maxSum(vector<int>& nums, int k, int mul) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        long long ans = 0;

        for (int i = n - 1; i >= n - k; --i) {
            int m = max(1, mul);
            ans += 1LL * nums[i] * m;
            mul--;
        }

        return ans;
    }
};

func maxSum(nums []int, k int, mul int) int64 {
    sort.Ints(nums)
    n := len(nums)
    var ans int64 = 0

    for i := n - 1; i >= n-k; i-- {
        m := max(1, mul)
        ans += int64(nums[i]) * int64(m)
        mul--
    }

    return ans
}

function maxSum(nums: number[], k: number, mul: number): number {
    nums.sort((a, b) => a - b);
    const n = nums.length;
    let ans = 0;

    for (let i = n - 1; i >= n - k; i--) {
        const m = Math.max(1, mul);
        ans += nums[i] * m;
        mul--;
    }

    return ans;
}

3974. K 个元素的最大总和

题目描述

解法

方法一：贪心 + 排序

评论