Tag

【贪心】【脑筋急转弯】【数组】【2023-11-15】

---

题目来源

2656. K 个元素的最大和

---

解题思路

方法一：贪心

从第一次操作开始每次选择数组中的最大值，由于最大值在加一后仍为数组中的最大值，所以若初始数组中的最大值为 m，则 k 次操作后我们能获得的分数为：

$$m+(m+1)+...+(m+k-1)=\frac{(2\ast m+k-1)\ast k}{2}$$

需要注意的是计算机中的 / 是整除，没有数学上的除法，需要考虑一上式结果为奇数还是偶数，现在分情况讨论一下：

• k 为偶数，则 k - 1 为奇数，奇数加偶数为奇数，所以 2 * m + k - 1 为奇数，奇数乘以偶数得到偶数，所以此时的结果为偶数；
• k 为奇数，则 k - 1 为偶数，偶数加偶数为偶数，所以 2 * m + k - 1 为奇数，奇数乘以偶数得到偶数，所以此时的结果为偶数。

综上，不论 k 是奇数还是偶数，最后的结果都是偶数，因此可以放心使用 /，最后返回 (2 * m + k - 1) * k / 2。

其实对于这种等差数列求和，只要数列中的数都是整数，求和就不会得到小数，因此上述的判断奇偶数可以省略。

实现代码

class Solution {
public:
    int maximizeSum(vector<int>& nums, int k) {
        int m = *max_element(nums.begin(), nums.end());
        return (2 * m + k - 1) * k / 2;
    }
};

复杂度分析

时间复杂度：$O(1)$。

空间复杂度：$O(1)$。

其他语言

C

int maximizeSum(int* nums, int numsSize, int k) {
    int m = 0;
    for (int i = 0; i < numsSize; i++) {
        m = fmax(m, nums[i]);
    }
    return (2 * m + k - 1) * k / 2; 
}

fmax 是 C 标准库中的一个函数，主要用于比较两个浮点数的大小，返回两者中的较大值。在函数原型中，fmax 接受两个 double 类型的参数。但是似乎也可以取出两个 int 类型元素的最大值。其实是将两个int类型数据传递给 fmax 时，被 fmax 加上小数点和 0 强转成浮点类型了，最后的输出浮点类型又被传给 int 类型，浮点类型被截断去掉小数点和 0，并不影响结果。所以以后在 c 语言中可以使用 fmax 来获得两个 int 类型数据的最大值，不要忘记头文件 #include<maxth.h>。

python3

class Solution:
    def maximizeSum(self, nums: List[int], k: int) -> int:
        return (2 * max(nums) + k - 1) * k // 2

---

写在最后

如果文章内容有任何错误或者您对文章有任何疑问，欢迎私信博主或者在评论区指出 💬💬💬。

如果大家有更优的时间、空间复杂度方法，欢迎评论区交流。

最后，感谢您的阅读，如果感到有所收获的话可以给博主点一个 👍 哦。