数组非相邻元素最大和的元素追踪及优化实现技术问询

Hey there! 你已经用inclusive/exclusive sum的思路搞定了最大和的计算，现在要追踪构成这个最大和的具体非相邻元素，还要处理sum相等时选元素更多集合的情况，对吧？我给你两个实用的方案，帮你高效解决这个问题～

核心思路 #

我们不需要维护所有可能的元素集合（那会导致空间爆炸），只需要同步维护与i_sum、e_sum对应的最优元素集合/选择标记——因为每一步的最优解只依赖于前一步的两个状态（包含前一个元素、不包含前一个元素），所以只需要跟踪这两个状态的最优情况就够了。

方案1：直观维护最优元素集合（适合中小规模数组） #

这种方法直接把i_sum和e_sum扩展成包含「当前和」与「对应元素列表」的结构，每次迭代时同步更新元素列表，逻辑非常直观：

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

using namespace std;

int main() {
    // 示例1：vector<int> tickets = {100,-3,200,50,400,-7,20,80};
    // 示例2：vector<int> tickets = {4,5,4,3};
    vector<int> tickets = {100,-3,200,50,400,-7,20,80};
    int n = tickets.size();
    if (n == 0) return 0;

    // 初始化：包含第一个元素的状态（sum+元素列表）
    pair<int, vector<int>> incl = {tickets[0], {tickets[0]}};
    // 初始化：不包含第一个元素的状态
    pair<int, vector<int>> excl = {0, {}};

    for (int i = 1; i < n; i++) {
        pair<int, vector<int>> new_excl;
        // 确定新的exclusive状态：取前一步incl/excl的最优解
        if (incl.first > excl.first) {
            new_excl = incl;
        } else if (incl.first < excl.first) {
            new_excl = excl;
        } else {
            // sum相等时，选元素数量更多的集合
            new_excl = (incl.second.size() > excl.second.size()) ? incl : excl;
        }

        // 新的inclusive状态：前一步的exclusive加上当前元素
        pair<int, vector<int>> new_incl = {excl.first + tickets[i], excl.second};
        new_incl.second.push_back(tickets[i]);

        // 更新状态
        incl = new_incl;
        excl = new_excl;
    }

    // 确定最终的最优结果
    pair<int, vector<int>> result;
    if (incl.first > excl.first) {
        result = incl;
    } else if (incl.first < excl.first) {
        result = excl;
    } else {
        result = (incl.second.size() > excl.second.size()) ? incl : excl;
    }

    // 逆序输出元素
    cout << "最大和：" << result.first << endl;
    cout << "逆序输出元素：";
    for (auto it = result.second.rbegin(); it != result.second.rend(); ++it) {
        cout << *it << (next(it) == result.second.rend() ? "" : ", ");
    }
    cout << endl;

    return 0;
}

优点与注意事项

• 逻辑清晰，容易理解和调试；
• 每次迭代会复制元素列表，对于超大数组（如10万级以上）会有一定性能开销，但绝大多数场景下完全够用。

方案2：回溯标记法（适合大规模数组，空间更高效） #

如果数组规模很大，我们可以用标记数组记录每个元素的选择状态，最后通过回溯收集元素，避免频繁的列表复制：

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

using namespace std;

// 辅助函数：计算sum和对应的元素数量
void calcSumAndCount(const vector<int>& tickets, vector<int>& i_sum, vector<int>& e_sum, vector<int>& i_count, vector<int>& e_count) {
    int n = tickets.size();
    i_sum[0] = tickets[0];
    e_sum[0] = 0;
    i_count[0] = 1;
    e_count[0] = 0;

    for (int i = 1; i < n; i++) {
        // 更新e_sum和e_count
        if (i_sum[i-1] > e_sum[i-1]) {
            e_sum[i] = i_sum[i-1];
            e_count[i] = i_count[i-1];
        } else if (i_sum[i-1] < e_sum[i-1]) {
            e_sum[i] = e_sum[i-1];
            e_count[i] = e_count[i-1];
        } else {
            e_sum[i] = i_sum[i-1];
            e_count[i] = max(i_count[i-1], e_count[i-1]);
        }
        // 更新i_sum和i_count
        i_sum[i] = e_sum[i-1] + tickets[i];
        i_count[i] = e_count[i-1] + 1;
    }
}

int main() {
    // 示例1：vector<int> tickets = {100,-3,200,50,400,-7,20,80};
    // 示例2：vector<int> tickets = {4,5,4,3};
    vector<int> tickets = {4,5,4,3};
    int n = tickets.size();
    if (n == 0) return 0;

    vector<int> i_sum(n), e_sum(n), i_count(n), e_count(n);
    calcSumAndCount(tickets, i_sum, e_sum, i_count, e_count);

    // 确定最终状态：是否以包含最后一个元素结束
    bool end_with_incl;
    int max_sum;
    if (i_sum[n-1] > e_sum[n-1]) {
        max_sum = i_sum[n-1];
        end_with_incl = true;
    } else if (i_sum[n-1] < e_sum[n-1]) {
        max_sum = e_sum[n-1];
        end_with_incl = false;
    } else {
        max_sum = i_sum[n-1];
        end_with_incl = (i_count[n-1] > e_count[n-1]);
    }

    // 回溯收集元素
    vector<int> result;
    int i = n-1;
    while (i >= 0) {
        if (end_with_incl) {
            result.push_back(tickets[i]);
            // 选了当前元素，前一个元素必须不选
            end_with_incl = false;
            i--;
        } else {
            if (i == 0) break;
            // 判断前一步选incl还是excl
            if (i_sum[i-1] > e_sum[i-1]) {
                end_with_incl = true;
            } else if (i_sum[i-1] < e_sum[i-1]) {
                end_with_incl = false;
            } else {
                end_with_incl = (i_count[i-1] > e_count[i-1]);
            }
            i--;
        }
    }

    // 输出结果
    cout << "最大和：" << max_sum << endl;
    cout << "逆序输出元素：";
    for (size_t j = 0; j < result.size(); j++) {
        cout << result[j] << (j == result.size()-1 ? "" : ", ");
    }
    cout << endl;

    return 0;
}

优点与注意事项

• 空间复杂度为O(n)，时间复杂度O(n)，适合超大数组；
• 需要额外维护元素数量的数组，逻辑比第一种稍复杂，但性能更优。

对你疑问的解答 #

• 绝对不要维护所有可能值：这会导致空间复杂度指数级增长，完全不现实；
• 推荐选择上述两种方案：它们都是在遍历过程中只维护当前的两个最优状态（包含/不包含当前元素），要么同步更新元素列表，要么记录回溯标记，高效且可控。

这两种方案都能完美处理你给出的示例：

• 示例1会输出 80,400,200,100；
• 示例2会输出 4,4。

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