求无相邻元素最大和子序列提交出错，恳请排查遗漏测试用例

首先，先明确你要解决的问题要求：

给定由N个正整数组成的数组arr[]，找出一个子序列，使其和最大且子序列中无数组相邻元素。
输入格式：第一行输入测试用例数T；每个测试用例第一行输入数组大小N，下一行输入N个空格分隔的数组元素。
输出格式：每个测试用例输出符合要求的子序列的最大和。
约束条件：1 ≤ T ≤ 100，1 ≤ N ≤ 10^6，1 ≤ arr[i] ≤ 10^6

你提到自己的测试用例能正常运行，但提交时显示答案错误，结合你的代码和问题约束，我帮你找到了几个核心问题：

1. 整数溢出问题（最致命的错误） #

你的所有求和变量（sum_even、sum_odd、sum1、sum2、sum）都使用了int类型，但根据约束条件，最大可能的总和是1e6 * 1e6 = 1e12，而int的最大范围仅为约2e9，远不足以存储这么大的数值。当总和超过int的上限时，会发生溢出，导致计算结果变成错误的负数或随机值，这直接导致提交答案错误。

2. 栈溢出风险 #

你使用了变长数组int arr[n];在栈上分配内存，栈的大小通常只有几MB，当n=1e6时，1e6个int需要4MB内存，刚好接近栈的极限，很容易导致栈溢出，程序崩溃后输出错误结果。

3. 逻辑覆盖不全（部分测试用例会出错） #

你的代码仅枚举了几种特定的选法（全选偶数下标、全选奇数下标、从第一个元素开始偶尔跳选、从第二个元素开始偶尔跳选），虽然在多数正整数数组中能得到正确结果，但并非所有情况都适用。比如这个测试用例：

输入：
1
5
100 1 1 100 100

正确的最大和是100（下标0） + 100（下标3）=200？不，不对——下标3和4相邻，不能同时选，正确的最大和应该是100（下标0） + 100（下标4）=200？或者100（下标1？不，下标1是1）哦，正确的最优解是100（下标0） + 100（下标3）=200？不对，下标0和3不相邻，可以选，而下标3和4相邻，所以不能选3和4。你的代码虽然能处理这个情况，但如果遇到更复杂的跳选场景，逻辑可能会失效。

修正后的正确解法（动态规划） #

解决这个问题的标准方法是动态规划，时间复杂度O(n)，空间复杂度可以优化到O(1)，同时避免上述所有问题：

优化版代码（边输入边计算，无需存储整个数组） #

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); // 加速输入，适配1e6级别的大输入

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;

        long long prev_prev = 0, prev = 0;
        for (int i = 0; i < n; ++i) {
            int num;
            cin >> num;
            // 当前元素的最优选择：选它（加前前一个的最大和）或不选它（等于前一个的最大和）
            long long current = max(prev, prev_prev + num);
            prev_prev = prev;
            prev = current;
        }
        cout << prev << '\n';
    }
    return 0;
}

动态规划思路解释 #

• prev_prev：表示处理到前i-2个元素时的最大和
• prev：表示处理到前i-1个元素时的最大和
• 对于当前元素，有两种选择：
  1. 选它：那么总和是prev_prev + 当前元素（不能选前一个元素）
  2. 不选它：那么总和等于prev（继承前i-1个元素的最大和）
• 取两种选择的最大值作为当前的最优解，迭代更新即可。

这个解法完全覆盖了所有可能的选法，同时用long long存储总和避免溢出，边输入边计算避免栈溢出，完美适配题目约束。

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