Java递归无额外参数保存值及数组最大对向和求解问题

问题需求 #

编写递归方法，计算数组中对向元素的最大和（即首元素与尾元素相加、次首元素与次尾元素相加……），例如数组{2,2,4,5}的计算结果为7（2+5=7，2+4=6，取最大值）。要求仅使用数组、起始索引start、结束索引end作为方法参数，不能新增参数。

原代码问题 #

你当前的代码将所有对向元素的和进行了累加，而非找出其中的最大值：

private static int findMaxOppositeSum(int[] sequence, int start, int end) {
    if (start >= end) {
        return 0;
    }
    return sequence[start] + sequence[end] + findMaxOppositeSum(sequence, start + 1, end - 1);
}

修正后的代码 #

调整递归逻辑，每次比较当前对向元素的和与后续递归得到的最大值，返回两者中的较大值：

private static int findMaxOppositeSum(int[] sequence, int start, int end) {
    // 终止条件：无配对元素时返回极小值，不参与最大值比较
    if (start >= end) {
        return Integer.MIN_VALUE;
    }
    // 计算当前配对的和
    int currentPairSum = sequence[start] + sequence[end];
    // 递归获取后续配对的最大和
    int maxFromRest = findMaxOppositeSum(sequence, start + 1, end - 1);
    // 返回当前和与后续最大和中的较大值
    return Math.max(currentPairSum, maxFromRest);
}

逻辑说明 #

1. 终止条件：当start >= end时，说明没有可配对的元素，返回Integer.MIN_VALUE（确保不会干扰正常配对和的最大值比较）。
2. 当前配对计算：算出当前start和end指向的元素和。
3. 递归传递：调用自身处理剩余的子数组，得到剩余部分的最大对向和。
4. 取最大值：比较当前配对和与剩余部分的最大值，返回较大的那个，最终递归结束时就能得到整个数组的最大对向元素和。

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