最多跳过一个连续元素的最大子序列和递归解法问题排查

问题背景 #

需求是找出满足以下条件的连续子序列最大和：

• 子序列必须是连续的；
• 最多可跳过一个元素（即在连续段中允许跳过其中一个元素）。

测试示例：

• 输入[-3,2,4,-1,-2,-5]，预期输出4；
• 输入[9,-1,-3,4,5]，预期输出17（对应子序列9,-1,4,5，跳过-3）。

当前Java递归实现第一个示例正确，但第二个示例输出26而非17，以下是错误分析和修正方案。

原代码：

public static void main(String[] args) {
    int[] arr={9,-1,-3,4,5};
    int n=arr.length;
    System.out.print(solve(n-1,arr,0));
}
public static int solve(int ind,int[] arr,int skip){
    if(ind==-1 && skip==0)
        return arr[ind+1];
    
    if(ind==-1 && skip==1)
        return 0;
    
    if(skip>1)
        return Integer.MIN_VALUE;
    
    int notpick=0;
    int pick=arr[ind]+solve(ind-1,arr,0);
    if(skip<2)
        notpick=solve(ind-1,arr,skip+1);
    
    return Math.max(pick,notpick);
}

核心错误点 #

1. 终止条件逻辑混乱
   当ind==-1且skip==0时返回arr[0]完全错误，这会导致遍历完所有元素时，强制返回第一个元素的值，干扰正常的累加逻辑，甚至在空序列场景下返回无效值。

2. pick分支破坏状态连续性
   pick的实现arr[ind]+solve(ind-1,arr,0)强制将skip重置为0，丢失了之前的跳过状态，既无法正确处理“跳过一个元素后继续选择后续元素”的场景，还会错误累加非连续的元素（比如把前后不相关的元素无理由相加），直接导致第二个示例的错误结果。

3. notpick初始值不合理
   notpick默认设为0，当无法跳过元素时（skip已为1），这个0会被纳入最大值比较，引入无效的空序列值，干扰正确结果。

4. 未遵守“连续子序列”约束
   原逻辑没有区分“开启新子序列”和“延续当前子序列”，导致递归中会组合非连续的元素，完全违背了子序列必须连续的要求。

修正后的递归实现 #

调整递归逻辑，维护两个关键状态：是否正在连续子序列中、已跳过元素数量，同时全局跟踪所有可能的最大和：

public class MaxSubSeqSum {
    private static int globalMax;

    public static void main(String[] args) {
        int[] arr = {9, -1, -3, 4, 5};
        globalMax = Integer.MIN_VALUE;
        // 初始化递归，同时处理单个元素的极端情况
        solve(arr.length - 1, arr, false, 0);
        for (int num : arr) {
            globalMax = Math.max(globalMax, num);
        }
        System.out.println(globalMax);
    }

    // 返回以ind索引元素结尾的子序列最大和
    // inSeq: 是否处于连续子序列中
    // skipCnt: 已跳过的元素数量
    private static int solve(int ind, int[] arr, boolean inSeq, int skipCnt) {
        if (ind < 0) {
            // 遍历完所有元素，处于序列中返回0（无额外贡献），否则返回负无穷（无效）
            return inSeq ? 0 : Integer.MIN_VALUE;
        }

        // 选择当前元素：要么延续现有序列，要么开启新序列
        int take = Integer.MIN_VALUE;
        if (inSeq) {
            int prevSum = solve(ind - 1, arr, true, skipCnt);
            if (prevSum != Integer.MIN_VALUE) {
                take = arr[ind] + prevSum;
            }
        } else {
            take = arr[ind];
        }
        globalMax = Math.max(globalMax, take);

        // 跳过当前元素：仅当处于序列中且未跳过元素时允许
        int skip = Integer.MIN_VALUE;
        if (inSeq && skipCnt < 1) {
            skip = solve(ind - 1, arr, true, skipCnt + 1);
            globalMax = Math.max(globalMax, skip);
        }

        // 返回当前索引结尾的最大可能值，供上层递归使用
        return Math.max(take, skip);
    }
}

修正逻辑说明 #

• 状态清晰化：用inSeq确保只处理连续的子序列，skipCnt严格控制跳过次数不超过1；
• 全局最大值跟踪：递归过程中实时更新globalMax，覆盖所有可能的连续子序列（包括跳过一个元素的情况）；
• 分支逻辑严谨：
  • take分支：要么延续之前的连续序列，要么从当前元素开启新序列；
  • skip分支：仅在已处于连续序列中且未跳过元素时，允许跳过当前元素并继续延续序列；
• 极端情况处理：单独遍历数组，确保所有元素为负数时，返回最大的单个元素。

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