不含三个相关元素的递归最大子序列和

Question

我试图用递归的方法来解决一个最大化子序列和的方法，这样就没有三个元素是连续的。

有一种方法可以通过动态编程来实现这一点，但我想首先使用递归来构建它。

一些示例输入和输出：

Input:{1, 2, 3}
Output: 5

Input:{100, 1000, 100, 1000, 1}
Output: 2101

Input:{1, 2, 3, 4, 5, 6, 7, 8}
Output: 27

int maxSubsequenceSum(vector<int> nums)
{
    return helper(nums, nums.size());
}

int helper(vector<int>& nums, int index)
{
    if (index <= 0) return 0;

    int withoutThird = helper(nums, index - 3) + nums[index - 1] + nums[index - 2];
    int withoutSecond = helper(nums, index - 3) + (index - 1 < 0 ? 0 : nums[index - 1]) + (index - 3 < 0 ? 0 : nums[index - 3]);
    int withoutFirst = helper(nums, index - 3) + (index - 2 < 0 ? 0 : nums[index - 2]) + (index - 3 < 0 ? 0 : nums[index - 3]);
    return max(withoutThird, max(withoutSecond, withoutFirst));
}

单独地，withoutThird、withoutSecond和withoutFirst三个变量只在递归排列失败时给出正确的结果。为什么它会失败，这是正确的递归方法吗？

Answer 1

问题是在没有三个连续元素的情况下获得最大值。

你要做的是，一次取3个元素，从中选择两个有最大和的元素，然后把它们相加，等等。

当你的递归从右到左。
假设{D,E,F}
(D+E)>E+F和(D+E)>(D+F)
您的代码将从最后3个元素中选择{D,E}。现在，假设{A,B,C}
假设(B+C)>(A+B)和(B+C)>(A+C)
您的代码将从前3个元素中选择{B,C}。