数组两个不重叠连续区间收集最大硬币的高效算法求解

给定长度为N的整数数组A，每个元素代表一行中每个box上的coins数量，整数K和L分别代表robo1和robo2收集时可选择的盒子数量，要求二者选择的区间完全不重叠，返回它们可收集的最大硬币总数，不存在合法区间时返回-1。

示例1：输入A = [6, 1, 4, 6, 3, 2, 7, 4]，K = 3，L = 2，输出为24。其中robo1选择第3到5个盒子，收集4+6+3=13枚硬币，robo2选择第7到8个盒子，收集7+4=11枚硬币，总和24为最大值。
示例2：输入A = [10, 19, 15]，K = 2，L = 2，输出为-1，因为无法选出两个不重叠的长度为2的区间。

原实现存在的问题 #

• 逻辑bug：仅在K > L时给highest和lowest赋值，当K <= L时两个变量保持初始值0，后续循环逻辑完全错误，直接导致非K>L的用例返回错误结果。
• 贪心逻辑缺陷：仅选取全局最大的长区间后再找短区间最大值，未覆盖所有可能的区间组合，当存在多个相同最大值的长区间、或数组包含负数元素时，会得到错误的总和。
• 性能低下：每次计算区间和都需要复制子数组再通过流求和，单次求和时间复杂度为O(K)或O(L)，整体时间复杂度达到O(N*(K+L))，且频繁复制数组产生大量额外内存开销，N较大时会严重超时。

优化方案（时间复杂度O(N)，空间复杂度O(N)） #

实现思路 #

1. 首先预处理前缀和数组，将任意区间和的计算复杂度降到O(1)。前缀和数组preSum定义为：preSum[0] = 0，preSum[i] = preSum[i-1] + A[i-1]，则区间[a, b)（长度为b-a）的和为preSum[b] - preSum[a]。
2. 两个不重叠区间只有两种位置关系：K长度区间在L长度区间左侧、L长度区间在K长度区间左侧，分别计算两种场景的最大总和，取二者最大值即可。
3. 遍历每个可能的右区间位置时，同步维护左侧已遍历范围的最大区间和，避免重复计算。

代码实现 #

import java.util.Arrays;

public class MaxCoins {
    public static int getMaxCoins(int[] A, int K, int L) {
        int n = A.length;
        if (n < K + L) return -1;
        
        // 预处理前缀和
        int[] preSum = new int[n + 1];
        for (int i = 0; i < n; i++) {
            preSum[i+1] = preSum[i] + A[i];
        }
        
        // 情况1：K长度区间在L长度区间左侧
        int max1 = getMax(preSum, K, L);
        // 情况2：L长度区间在K长度区间左侧
        int max2 = getMax(preSum, L, K);
        
        return Math.max(max1, max2);
    }
    
    // 计算leftLen长度区间在rightLen长度区间左侧时的最大总和
    private static int getMax(int[] preSum, int leftLen, int rightLen) {
        int maxLeft = 0;
        int res = 0;
        int n = preSum.length - 1;
        // 右区间的起始位置i最小为leftLen，最大为n - rightLen
        for (int i = leftLen; i <= n - rightLen; i++) {
            // 更新左侧leftLen长度区间的最大值
            maxLeft = Math.max(maxLeft, preSum[i] - preSum[i - leftLen]);
            // 当前右区间的和 + 左侧最大值
            int current = maxLeft + (preSum[i + rightLen] - preSum[i]);
            res = Math.max(res, current);
        }
        return res;
    }

    public static void main(String[] args) {
        // 测试示例1
        int[] A1 = {6,1,4,6,3,2,7,4};
        System.out.println(getMaxCoins(A1, 3, 2)); // 输出24
        // 测试示例2
        int[] A2 = {10,19,15};
        System.out.println(getMaxCoins(A2, 2, 2)); // 输出-1
    }
}

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