当前位置：首页 > article >正文

LeetCode 2656 K个元素的最大和

article 2025/3/1 10:42:12

《最大化得分：数组操作的数学之美》

题目背景

在算法的世界里，我们常常会遇到各种各样有趣的问题，这些问题不仅考验我们的编程能力，更考验我们的数学思维和逻辑推理能力。今天，我们就来探讨一道这样的题目：给定一个下标从 0 开始的整数数组 nums 和一个整数 k，需要执行特定操作恰好 k 次，以最大化得分。

问题描述

具体操作规则如下：

从 nums 中选择一个元素 m。
将选中的元素 m 从数组中删除。
将新元素 m + 1 添加到数组中。
得分增加 m。

我们的目标是返回执行以上操作恰好 k 次后的最大得分。

思路分析

贪心策略

要想获得最大得分，每次操作时我们应该选择数组中当前最大的元素。因为每次操作后得分增加的是当前选择的元素 m，选择越大的元素，得分增加得就越多。而且，当我们每次都选择最大元素时，下一次选择的元素也会尽可能大，这样就能保证最终的得分是最大的。

数学推导

假设数组中的最大元素为 max。第一次操作时，我们选择 max，得分增加 max，然后数组中该元素变为 max + 1；第二次操作，我们选择 max + 1，得分增加 max + 1，以此类推。执行 k 次操作后，我们得到的得分是一个首项为 max，公差为 1，项数为 k 的等差数列的和。

根据等差数列求和公式： $S_{n}=n*a_{1}+\frac{n*(n-1)*d}{2}$ ，其中 $S_{n}$ 是前 n项和，n是项数， $a_{1}$ 是首项，d是公差。在本题中，n=k， $a_{1}=max$ ，d=1，所以得分 $S=k*max+\frac{k*(K-1)}{2}$ 。

代码实现

以下是使用 C 语言实现的代码：

#include <stdio.h>

int maximizeSum(int* nums, int numsSize, int k) {
    int max = nums[0];
    // 找出数组中的最大值
    for (int i = 1; i < numsSize; i++) {
        if (nums[i] > max) {
            max = nums[i];
        }
    }
    // 等差数列求和公式：S = n * a1 + n * (n - 1) * d / 2
    // 这里 n = k, a1 = max, d = 1
    return k * max + k * (k - 1) / 2;
}