LeetCode 2656. K 个元素的最大和：一次遍历（附Python一行版代码）
【LetMeFly】2656.K 个元素的最大和：一次遍历（附Python一行版代码）
力扣题目链接：https://leetcode.cn/problems/maximum-sum-with-exactly-k-elements/
给你一个下标从 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
方法一：一次遍历
- 想要使和最大，每次操作肯定选最大值
- 每次操作后最大值都会更大
因此，我们只需要遍历一遍数组找到数组中元素的最大值，假设为 M M M，则返回等差数列 M , M + 1 , M + 2 , ⋯ , M + k − 1 M, M + 1, M + 2, \cdots, M + k - 1 M,M+1,M+2,⋯,M+k−1（共 k k k项）之和 k M + ( M + k − 1 ) 2 k\frac{M + (M + k - 1)}{2} k2M+(M+k−1)即为答案。
- 时间复杂度 O ( l e n ( n u m s ) ) O(len(nums)) O(len(nums))
- 空间复杂度 O ( 1 ) O(1) O(1)
AC代码
C++
class Solution {
public:int maximizeSum(vector<int>& nums, int k) {int M = nums[0];for (int t : nums) {M = max(M, t);}return k * (M + M + k - 1) / 2;}
};
Python
# from typing import Listclass Solution:def maximizeSum(self, nums: List[int], k: int) -> int:return k * (max(nums) * 2 + k - 1) // 2
同步发文于CSDN，原创不易，转载经作者同意后请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/134429024