力扣1031题指南：如何高效寻找两个不重叠子数组的最大和？

一、问题理解与解题思路

力扣1031题要求我们在一个整数数组中找到两个不重叠的、长度固定的子数组，使它们的和最大。这道题考察了动态规划和滑动窗口的综合应用能力。

关键点分析

1. 不重叠条件：两个子数组不能有任何重叠的元素

2. 固定长度：两个子数组的长度分别为firstLen和secondLen

3. 最大和：在所有可能的组合中，找出和最大的那一对

解题思路

1. 前缀和预处理：计算前缀和数组，方便快速计算任意子数组的和

2. 滑动窗口应用：使用滑动窗口技术计算所有可能子数组的和

3. 动态规划思想：记录从左到右和从右到左的子数组最大值

4. 组合比较：尝试两种可能的排列顺序（firstLen在前或secondLen在前）

二、代码实现详解

前缀和计算

前缀和数组prefixSum的构建是解决子数组和问题的经典方法。通过prefixSum[i+1] - prefixSum[i+1-len]可以快速计算长度为len的子数组和。

四个辅助数组

1. firstMax：记录从左到右到当前位置为止，firstLen长度的子数组最大和

2. secondMax：记录从左到右到当前位置为止，secondLen长度的子数组最大和

3. firstMaxFromRight：记录从右到左从当前位置开始，firstLen长度的子数组最大和

4. secondMaxFromRight：记录从右到左从当前位置开始，secondLen长度的子数组最大和

两种排列情况

1. firstLen在前：遍历所有可能的firstLen子数组，然后在其右侧找最大的secondLen子数组

2. secondLen在前：遍历所有可能的secondLen子数组，然后在其右侧找最大的firstLen子数组

三、完整代码

class Solution {
public:
    int maxSumTwoNoOverlap(vector<int>& nums, int firstLen, int secondLen) {
        int n = nums.size();
        vector<int> prefixSum(n + 1, 0);
        
        // 计算前缀和数组
        for (int i = 0; i < n; ++i) {
            prefixSum[i + 1] = prefixSum[i] + nums[i];
        }
        
        // 初始化四个数组用于记录不同情况下的最大值
        vector<int> firstMax(n, 0);    // 记录到i位置为止firstLen长度的子数组最大值
        vector<int> secondMax(n, 0);   // 记录到i位置为止secondLen长度的子数组最大值
        vector<int> firstMaxFromRight(n, 0);  // 记录从i位置开始往右firstLen长度的子数组最大值
        vector<int> secondMaxFromRight(n, 0); // 记录从i位置开始往右secondLen长度的子数组最大值
        
        // 从左到右计算firstMax和secondMax
        for (int i = firstLen - 1; i < n; ++i) {
            int currentSum = prefixSum[i + 1] - prefixSum[i + 1 - firstLen];
            if (i == firstLen - 1) {
                firstMax[i] = currentSum;
            } else {
                firstMax[i] = max(firstMax[i - 1], currentSum);
            }
        }
        
        for (int i = secondLen - 1; i < n; ++i) {
            int currentSum = prefixSum[i + 1] - prefixSum[i + 1 - secondLen];
            if (i == secondLen - 1) {
                secondMax[i] = currentSum;
            } else {
                secondMax[i] = max(secondMax[i - 1], currentSum);
            }
        }
        
        // 从右到左计算firstMaxFromRight和secondMaxFromRight
        for (int i = n - firstLen; i >= 0; --i) {
            int currentSum = prefixSum[i + firstLen] - prefixSum[i];
            if (i == n - firstLen) {
                firstMaxFromRight[i] = currentSum;
            } else {
                firstMaxFromRight[i] = max(firstMaxFromRight[i + 1], currentSum);
            }
        }
        
        for (int i = n - secondLen; i >= 0; --i) {
            int currentSum = prefixSum[i + secondLen] - prefixSum[i];
            if (i == n - secondLen) {
                secondMaxFromRight[i] = currentSum;
            } else {
                secondMaxFromRight[i] = max(secondMaxFromRight[i + 1], currentSum);
            }
        }
        
        int result = 0;
        // 情况1：firstLen子数组在secondLen子数组左边
        for (int i = firstLen - 1; i < n - secondLen; ++i) {
            result = max(result, firstMax[i] + secondMaxFromRight[i + 1]);
        }
        
        // 情况2：secondLen子数组在firstLen子数组左边
        for (int i = secondLen - 1; i < n - firstLen; ++i) {
            result = max(result, secondMax[i] + firstMaxFromRight[i + 1]);
        }
        
        return result;
    }
};

四、常见错误与调试技巧

新手在实现这类问题时容易犯以下错误：

1. 边界条件处理不当：特别是数组越界问题

2. 重叠判断错误：没有正确确保子数组不重叠

3. 最大值更新逻辑错误：在构建辅助数组时更新条件不正确

调试建议：

• 使用小规模测试用例逐步验证

• 打印中间变量检查计算过程

• 特别注意边界索引的处理

五、总结

通过这道题目，我们学习了如何：

1. 综合应用前缀和、滑动窗口和动态规划技术

2. 处理复杂约束条件下的最优化问题

3. 设计高效的线性扫描算法

4. 分解复杂问题为多个可管理的子问题

掌握这些技巧对于解决数组相关的算法问题至关重要。