class Solution {
public:
int maximizeSum(vector<int>& nums, int k) {
}
};
2656. K 个元素的最大和
给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。你需要执行以下操作 恰好 k 次，最大化你的得分：
nums 中选择一个元素 m 。m 从数组中删除。m + 1 添加到数组中。m 。请你返回执行以上操作恰好 k 次后的最大得分。
示例 1：
输入：nums = [1,2,3,4,5], k = 3 输出：18 解释：我们需要从 nums 中恰好选择 3 个元素并最大化得分。 第一次选择 5 。和为 5 ，nums = [1,2,3,4,6] 。 第二次选择 6 。和为 6 ，nums = [1,2,3,4,7] 。 第三次选择 7 。和为 5 + 6 + 7 = 18 ，nums = [1,2,3,4,8] 。 所以我们返回 18 。 18 是可以得到的最大答案。
示例 2：
输入：nums = [5,5,5], k = 2 输出：11 解释：我们需要从 nums 中恰好选择 2 个元素并最大化得分。 第一次选择 5 。和为 5 ，nums = [5,5,6] 。 第二次选择 6 。和为 6 ，nums = [5,5,7] 。 所以我们返回 11 。 11 是可以得到的最大答案。
提示：
1 <= nums.length <= 1001 <= nums[i] <= 1001 <= k <= 100原站题解
cpp 解法, 执行用时: 32 ms, 内存消耗: 69.3 MB, 提交时间: 2023-11-15 22:28:13
class Solution {
public:
int maximizeSum(vector<int> &nums, int k) {
int m = *max_element(nums.begin(), nums.end());
return (m * 2 + k - 1) * k / 2;
}
};
rust 解法, 执行用时: 8 ms, 内存消耗: 2.1 MB, 提交时间: 2023-09-12 15:55:13
impl Solution {
pub fn maximize_sum(nums: Vec<i32>, k: i32) -> i32 {
let max_val = nums.into_iter().max().unwrap();
(max_val + max_val + k - 1) * k / 2
// nums.iter().max().unwrap() * k + (k - 1) * k / 2
}
}
java 解法, 执行用时: 1 ms, 内存消耗: 42.5 MB, 提交时间: 2023-09-12 15:54:09
class Solution {
public int maximizeSum(int[] nums, int k) {
int max = 0;
for (int num: nums) {
max = Math.max(max, num);
}
return (max + max + k - 1) * k / 2;
}
}
php 解法, 执行用时: 36 ms, 内存消耗: 18.7 MB, 提交时间: 2023-09-12 15:52:10
class Solution {
/**
* @param Integer[] $nums
* @param Integer $k
* @return Integer
*/
function maximizeSum($nums, $k) {
return intval((max($nums) * 2 + $k - 1) * $k / 2);
}
}
golang 解法, 执行用时: 36 ms, 内存消耗: 6.6 MB, 提交时间: 2023-05-05 15:52:22
func maximizeSum(nums []int, k int) int {
max := nums[0]
for _, x := range nums[1:] {
if x > max {
max = x
}
}
return (max*2 + k - 1) * k / 2
}
python3 解法, 执行用时: 56 ms, 内存消耗: 16 MB, 提交时间: 2023-05-05 15:52:08
class Solution:
def maximizeSum(self, nums: List[int], k: int) -> int:
return (max(nums) * 2 + k - 1) * k // 2