请求为求解非连续元素数组最大值的C++递归程序添加回溯功能

嘿，你的递归实现已经精准抓住了问题的核心逻辑——要么选当前元素然后跳过下一个，要么直接跳过当前元素去看下一个！要添加回溯功能记录选中的元素，我们只需要在计算最大值的同时，追踪每一步选择的路径就行。

核心思路 #

递归过程中，我们要同步完成两件事：

• 计算两种选择（选当前元素/不选当前元素）的最大和
• 根据计算结果，把最优路径上的元素记录下来

为了避免递归过程中状态混乱，我们让每个递归分支独立维护自己的选中元素列表，最后把最优分支的列表合并到最终结果里。

修改后的完整代码 #

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n;

int findMax(int x, int ar[], vector<int>& selected) {
    if (x >= n) {
        return 0;
    }

    // 分支1：选中当前元素，递归处理x+2位置
    vector<int> selectCurrent;
    int sumWithCurrent = ar[x] + findMax(x + 2, ar, selectCurrent);

    // 分支2：不选中当前元素，递归处理x+1位置
    vector<int> skipCurrent;
    int sumWithoutCurrent = findMax(x + 1, ar, skipCurrent);

    // 选择总和更大的分支，更新选中元素列表
    if (sumWithCurrent >= sumWithoutCurrent) {
        selected.push_back(ar[x]);
        // 把后续选中的元素追加进来
        selected.insert(selected.end(), selectCurrent.begin(), selectCurrent.end());
        return sumWithCurrent;
    } else {
        selected = skipCurrent;
        return sumWithoutCurrent;
    }
}

int main() {
    int ar[] = {1,7,4,4,9,5,12};
    n = sizeof(ar)/sizeof(ar[0]);
    vector<int> selectedElements;

    int maxTotal = findMax(0, ar, selectedElements);

    cout << "计算得到的最大和为：" << maxTotal << endl;
    cout << "选中的元素依次是：";
    for (int num : selectedElements) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

代码细节说明 #

• 给findMax函数新增了引用参数vector<int>& selected，用来存放当前分支选中的元素，确保递归过程中能持续更新同一个结果容器。
• 每个递归分支创建独立的临时vector（selectCurrent和skipCurrent），这样不同分支的选中状态不会互相干扰，避免了回溯时的状态混乱。
• 递归结束后，比较两个分支的总和：如果选当前元素的总和更大，就把当前元素加入结果列表，再追加后续分支选中的元素；否则直接复用不选当前元素分支的结果列表。
• 测试你提供的数组{1,7,4,4,9,5,12}，运行结果会输出最大和28，选中的元素是7 9 12，完全符合最优解的要求。

小提示 #

如果你的数组规模很大，递归可能会遇到栈溢出的问题，这时候可以考虑把递归改成动态规划的实现方式，同时记录路径。不过针对一般规模的数组，这个递归版本已经足够好用啦！

内容的提问来源于stack exchange，提问作者Anonymous