如何最大化总和？ [英] How to maximize the sum?

问题描述

我们得到了一个排序数组。

We are given a sorted array.

让 pass 的初始值为零。

我们可以多次执行以下操作：

We can do the following operation any number of times:

1. 选择任何一次 k 个数字。全部添加。将这个总和加到 pass

1. Select any k numbers at a time. Add them all up. Add this sum to pass

如果是数字，请说 x 是第一次从数组中选择 ，然后仅被视为 x 。当第二次选择它时，它被认为是 -x ，第三次它被认为是 x ，依此类推...

If a number, say x, is being selected for the first time from the array, then it is considered as x only. When it is selected for the second time, then it is considered as -x , and for the third time, again as x, and so on...

例如，让数组为 [-14、10、6，-6，-10，-10，-14] 和 k = 4 ，我们只会执行一次操作。我们选择以下4个数字： {14，10，6，-6} 。加起来，我们得到 24 。然后， pass = pass + 24 。因此，通过的最大值为 24 。

For example, let the array be [-14, 10, 6, -6, -10, -10, -14] and k = 4, and we'll only do the operation once. We select these 4 numbers: {14, 10, 6, -6}. Adding them up, we get 24. Then, pass=pass+24. Therefore, maximum value of pass is 24.

如何获取的最大值通过？

推荐答案

我们可以将问题重新表述如下：

We can reformulate the problem as follows:

我们有一个数字列表，我们可以激活或停用这些数字。我们想要找到激活数字的最大和，每次通过时我们都可以准确地切换 k 个数字。

We have a list of numbers and we can activate or deactivate the numbers. We want to find the maximum sum of activated numbers, where in each pass we can switch exactly k numbers.

对于奇数 k ，我们可以执行以下操作：激活最大数量（如果为正数），然后使用其余的（k-1）切换两次任何数字，这将有效地使数字保持其先前状态。因此，最大通行证值是正数之和。

For odd k, we could do the following: Activate the maximum number (if it is positive) and use the remaining (k-1) switches to switch any number twice, which will effectively leave the number in its previous state. Therefore, the maximum pass value is the sum of positive numbers.

对于 k ，这有点不同，因为激活号码的数量始终是偶数。因此，我们首先找到所有正数。假设正数为 p 。如果 p 是偶数，那么我们就很好了，这些数字的总和就是结果。如果 p 是奇数，我们必须检查两种情况：删除最小的正数或添加最大的非正数。这两种情况的最大值是结果。

For even k, this is slightly different since the number of activated numbers is always even. Therefore, we first find all positive numbers. Let the number of positive numbers be p. If p is even, then we are good and the sum of these numbers is the result. If p is odd, we have to check two cases: Remove the smallest positive number or add the largest non-positive number. The maximum of these two cases is the result.

根据评论编辑：

对于特殊情况，其中 k = n ，只有两个选择：要么包含所有数字，要么排除所有数字。如果数字的总和大于0，则为结果。否则，结果为0。

For the special case where k=n, there are only two options: Either include all numbers or exclude all numbers. If the sum of numbers is greater than 0, this is the result. Otherwise, the result is 0.

这篇关于如何最大化总和？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！