Leetcode 2965.K个元素的最大和
题目描述
给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。你需要执行以下操作 恰好 k 次,最大化你的得分:
- 从
nums中选择一个元素m。 - 将选中的元素
m从数组中删除。 - 将新元素
m + 1添加到数组中。 - 你的得分增加
m。
请你返回执行以上操作恰好 k 次后的最大得分。
1 | 示例 1: |
提示:
1 <= nums.length <= 1001 <= nums[i] <= 1001 <= k <= 100
解题方法
暴力
直接按照题意模拟 找到nums_\max 并执行次删除nums_\max并记录nums_\max的值
首先定义为答案 然后循环模拟
1 | class Solution: |
- 返回值不计入
数学
首先我们看回题意 可以得知 操作是 找到当前的值 -> 记录 -> 删除 -> 添加
那么下一次添加的值不就是上一个值的
因此我们设当前值为 即nums_\max=i
- 操作第次 为
- 操作第次 为
- 操作第次 为
- 操作第次 为
不难发现 这是一道规律题 得公式
问题来了如何算呢 我这里就拿来举例,即 设为数组的左边界 为数组的右边界 即
相当于数组的左右两边和是一样的 这样的和可以分为组
因此继续推理得到
当是奇数的时候 也是按同样的道理 加上它中间哪个数
最后 得出结论
示例代码
Python
1 | ## 时间复杂度O(n) |
C++
1 | // 时间复杂度O(n) |
