带记忆化的最大非相邻子序列和递归代码错误排查

问题背景 #

给定整数数组，寻找元素不相邻的子序列的最大和。例如输入{1,2,9,4,5,0,4,11,6}时，正确输出为26，对应子序列{1,9,5,11}。

原递归方法findMaxSumSubsequence运行正常，通过递归遍历所有子集（选择或不选择第i个元素）。但添加记忆化后的helper2方法存在逻辑错误：当输入nums={1,2}并调用helper2(nums,0,false)时，得到错误结果1，正确结果应为2。

原递归代码（正常运行） #

private int findMaxSumSubsequence(int[] arr ,int i ,boolean flag) {
    if( i>=arr.length)
        return 0;
    int incAns=0;
    if(!flag)
    {
        incAns=findMaxSumSubsequence(arr,i+1,true) + arr[i];
    }
    int exAns=findMaxSumSubsequence(arr,i+1,false) ;
    return Math.max(incAns, exAns);
}

带记忆化的错误代码 #

int[] memo = new int[101];
private  int helper2(int[] arr ,int i ,boolean flag) {
    if( i>=arr.length)
        return memo[i]=0;
    if(memo[i]!=-1)
        return memo[i];
    int incAns=0;
    if(!flag)
    {
        incAns=helper2(arr,i+1,true) + arr[i];
    }
    int exAns=helper2(arr,i+1,false) ;
    memo[i]= Math.max(incAns, exAns);
    return Math.max(incAns, exAns);
}

错误原因分析 #

问题核心是记忆化状态维度缺失：
原递归函数的状态由两个参数共同决定：当前索引i，以及前一个元素是否被选中的flag。但错误代码中仅用一维数组memo[i]存储结果，没有区分flag的两种状态，导致不同状态的结果被错误复用。

以输入{1,2}为例：

1. 调用helper2(0, false)时，先计算选择第一个元素的分支：调用helper2(1, true)，此时memo[1]被设为0（因为flag=true无法选择第二个元素，最大和为0）。
2. 接着计算不选第一个元素的分支：调用helper2(1, false)，此时发现memo[1]已被设为0，直接返回0，而实际上helper2(1, false)应该返回2（选择第二个元素）。最终取max(1,0)得到错误结果1。

修正后的记忆化代码 #

// 二维记忆数组：memo[i][0]表示到第i个元素且前一个未选中的最大和，memo[i][1]表示前一个已选中的最大和
int[][] memo;

private int helper2(int[] arr, int i, boolean flag) {
    if (i >= arr.length) {
        return 0;
    }
    // 将boolean类型的flag转为数组索引（0表示未选中前一个，1表示选中）
    int flagIdx = flag ? 1 : 0;
    if (memo[i][flagIdx] != -1) {
        return memo[i][flagIdx];
    }

    int incAns = 0;
    if (!flag) {
        // 前一个未选中时，可选择当前元素，递归时标记前一个已选中
        incAns = helper2(arr, i + 1, true) + arr[i];
    }
    // 不选择当前元素，递归时标记前一个未选中
    int exAns = helper2(arr, i + 1, false);

    int maxSum = Math.max(incAns, exAns);
    memo[i][flagIdx] = maxSum;
    return maxSum;
}

// 调用前需初始化记忆数组示例：
// memo = new int[arr.length][2];
// for (int[] row : memo) {
//     Arrays.fill(row, -1);
// }
// int result = helper2(arr, 0, false);

修正说明 #

• 使用二维数组memo[i][flagIdx]存储每个(i, flag)组合对应的最大和，彻底避免不同状态的结果混淆。
• 初始化时需将二维数组的所有元素设为-1，确保未计算过的状态会触发递归计算。

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