根据规则寻找最大和

Question

我必须根据规则找到整数数组中元素的最大总和：

如果将第二个（或任何连续的）元素添加到总和中 - 仅添加一半的值。为避免这种情况，您可以跳过一个元素。

例如我们有这样的输入 [4, 2, 5, 1, 5] 结果应该是 14。在这种情况下，我们取了 0、2 和 4 位置的元素（4 + 5 + 5 = 14），并跳过了位置 1 和 3 的元素

另一个例子是输入 [3, 1, 10, 6, 3, 10] 在这种情况下，答案应该是 26。我们取了位置 0、2、3、5 的元素，并跳过了位置 1 和 4 的元素。因此总和计算为：

3 + 0 + 10 + 6/2 + 0 + 10 = 26

谁能给我解释一下解决这个问题的算法？或者至少是我应该尝试解决它的方向。这个任务与动态规划有什么关系吗？或者可能使用递归？

提前致谢

Answer 1

一个简单的最佳解决方案是迭代计算两个总和，两者都对应于当前索引 i 的最大值，假定当前值 arr[i] 未被使用的第一个总和 (sum0)，假定当前值 arr[i] 被使用的第二个总和 (sum1)。

    sum0_new = max (sum0, sum1);
    sum1_new = max (sum0 + x, sum1 + x/2);

复杂度： O(N)

代码：

这是用于说明算法的简单 C++ 代码。
此实现假定整数除法 par 2。如果不是这种情况，则易于修改。

输出：14 26

#include <iostream>
#include <vector>
#include <algorithm>

int max_sum (const std::vector<int>& arr) {
    int sum0 = 0; 
    int sum1 = 0; 
    for (int x: arr) {
        int temp = sum0;
        sum0 = std::max (sum0, sum1);
        sum1 = std::max (temp + x, sum1 + x/2);
    }
    return std::max (sum0, sum1);
}

int main() {
    std::vector<std::vector<int>> examples = {
        {4, 2, 5, 1, 5},
        {3, 1, 10, 6, 3, 10}
    };
    for (std::vector<int>& arr: examples) {
        int sum = max_sum (arr);
        std::cout << sum << '\n';
    }
    return 0;
}

根据规则寻找最大和

Finding max sum according to rule

arrays

algorithm

sum

max