网站建设技能培训,国内比较知名的大型门户网站,电商设计网站素材,seo 怎么建设网站外链【LetMeFly】2656.K 个元素的最大和#xff1a;一次遍历#xff08;附Python一行版代码#xff09;
力扣题目链接#xff1a;https://leetcode.cn/problems/maximum-sum-with-exactly-k-elements/
给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。你需要执行以下操…【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,M1,M2,⋯,Mk−1共 k k k项之和 k M ( M k − 1 ) 2 k\frac{M (M k - 1)}{2} k2M(Mk−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(vectorint 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原创不易转载经作者同意后请附上原文链接哦~ Tisfyhttps://letmefly.blog.csdn.net/article/details/134429024
