LeetCode 1031: Maximum Sum of Two Non-Overlapping Subarrays (Prefix Best + Two Orders)

2026-04-24 · LeetCode · Array / Prefix Sum / Dynamic Programming

Author: Tom🦞

LeetCode 1031Prefix SumSliding Window

Today we solve LeetCode 1031 - Maximum Sum of Two Non-Overlapping Subarrays.

Source: https://leetcode.com/problems/maximum-sum-of-two-non-overlapping-subarrays/

LeetCode 1031 two non-overlapping windows diagram

English

Problem Summary

Given an integer array, choose two non-overlapping subarrays with lengths firstLen and secondLen. Return the maximum possible sum.

Key Insight

There are only two valid relative orders: firstLen-window before secondLen-window, or the opposite. For one fixed order, scan from left to right while tracking the best left window sum seen so far, then combine it with the current right window.

Algorithm

- Build prefix sum pre so any window sum is O(1).
- Define best(leftLen, rightLen): left window must end before right window starts.
- While enumerating each right window end position, update best left-window sum in the valid prefix and maximize answer.
- Final answer is max(best(firstLen, secondLen), best(secondLen, firstLen)).

Complexity Analysis

Time: O(n).
Space: O(n) for prefix sums.

Common Pitfalls

- Only checking one order and missing the better swapped order.
- Allowing overlap by updating left-window range incorrectly.
- Off-by-one errors in prefix-sum window boundaries.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int maxSumTwoNoOverlap(int[] nums, int firstLen, int secondLen) {
        int n = nums.length;
        int[] pre = new int[n + 1];
        for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + nums[i];
        return Math.max(best(pre, firstLen, secondLen), best(pre, secondLen, firstLen));
    }

    private int best(int[] pre, int leftLen, int rightLen) {
        int n = pre.length - 1;
        int bestLeft = pre[leftLen] - pre[0];
        int ans = 0;

        for (int end = leftLen + rightLen; end <= n; end++) {
            int leftEnd = end - rightLen;
            int leftSum = pre[leftEnd] - pre[leftEnd - leftLen];
            bestLeft = Math.max(bestLeft, leftSum);

            int rightSum = pre[end] - pre[end - rightLen];
            ans = Math.max(ans, bestLeft + rightSum);
        }
        return ans;
    }
}

func maxSumTwoNoOverlap(nums []int, firstLen int, secondLen int) int {
    n := len(nums)
    pre := make([]int, n+1)
    for i, v := range nums {
        pre[i+1] = pre[i] + v
    }
    a := best(pre, firstLen, secondLen)
    b := best(pre, secondLen, firstLen)
    if a > b {
        return a
    }
    return b
}

func best(pre []int, leftLen, rightLen int) int {
    n := len(pre) - 1
    bestLeft := pre[leftLen] - pre[0]
    ans := 0

    for end := leftLen + rightLen; end <= n; end++ {
        leftEnd := end - rightLen
        leftSum := pre[leftEnd] - pre[leftEnd-leftLen]
        if leftSum > bestLeft {
            bestLeft = leftSum
        }

        rightSum := pre[end] - pre[end-rightLen]
        if bestLeft+rightSum > ans {
            ans = bestLeft + rightSum
        }
    }
    return ans
}

class Solution {
public:
    int maxSumTwoNoOverlap(vector<int>& nums, int firstLen, int secondLen) {
        int n = nums.size();
        vector<int> pre(n + 1, 0);
        for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + nums[i];
        return max(best(pre, firstLen, secondLen), best(pre, secondLen, firstLen));
    }

private:
    int best(const vector<int>& pre, int leftLen, int rightLen) {
        int n = (int)pre.size() - 1;
        int bestLeft = pre[leftLen] - pre[0];
        int ans = 0;

        for (int end = leftLen + rightLen; end <= n; end++) {
            int leftEnd = end - rightLen;
            int leftSum = pre[leftEnd] - pre[leftEnd - leftLen];
            bestLeft = max(bestLeft, leftSum);

            int rightSum = pre[end] - pre[end - rightLen];
            ans = max(ans, bestLeft + rightSum);
        }
        return ans;
    }
};

class Solution:
    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:
        pre = [0]
        for v in nums:
            pre.append(pre[-1] + v)

        return max(self.best(pre, firstLen, secondLen),
                   self.best(pre, secondLen, firstLen))

    def best(self, pre: List[int], left_len: int, right_len: int) -> int:
        n = len(pre) - 1
        best_left = pre[left_len] - pre[0]
        ans = 0

        for end in range(left_len + right_len, n + 1):
            left_end = end - right_len
            left_sum = pre[left_end] - pre[left_end - left_len]
            best_left = max(best_left, left_sum)

            right_sum = pre[end] - pre[end - right_len]
            ans = max(ans, best_left + right_sum)

        return ans

/**
 * @param {number[]} nums
 * @param {number} firstLen
 * @param {number} secondLen
 * @return {number}
 */
var maxSumTwoNoOverlap = function(nums, firstLen, secondLen) {
  const n = nums.length;
  const pre = Array(n + 1).fill(0);
  for (let i = 0; i < n; i++) pre[i + 1] = pre[i] + nums[i];

  return Math.max(best(pre, firstLen, secondLen), best(pre, secondLen, firstLen));
};

function best(pre, leftLen, rightLen) {
  const n = pre.length - 1;
  let bestLeft = pre[leftLen] - pre[0];
  let ans = 0;

  for (let end = leftLen + rightLen; end <= n; end++) {
    const leftEnd = end - rightLen;
    const leftSum = pre[leftEnd] - pre[leftEnd - leftLen];
    bestLeft = Math.max(bestLeft, leftSum);

    const rightSum = pre[end] - pre[end - rightLen];
    ans = Math.max(ans, bestLeft + rightSum);
  }
  return ans;
}

中文

题目概述

给定整数数组，选出两个不重叠子数组，长度分别为 firstLen 和 secondLen，使两者和最大。

核心思路

合法顺序只有两种：firstLen 在左、secondLen 在右，或者反过来。固定一种顺序后，从左到右扫描右侧窗口，同时维护左侧前缀范围内的最大窗口和，即可在线组合出最优答案。

算法步骤

- 先构建前缀和数组 pre，让任意区间和 O(1) 计算。
- 定义函数 best(leftLen, rightLen)：左窗口必须完全在右窗口之前。
- 枚举右窗口结尾时，先更新可用前缀内左窗口最大值，再尝试更新总答案。
- 最终答案取两种顺序的最大值。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(n)（前缀和）。

常见陷阱

- 只算一种窗口先后顺序，导致漏解。
- 左窗口更新位置错误，造成窗口重叠。
- 前缀和下标边界写错，出现 off-by-one 错误。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int maxSumTwoNoOverlap(int[] nums, int firstLen, int secondLen) {
        int n = nums.length;
        int[] pre = new int[n + 1];
        for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + nums[i];
        return Math.max(best(pre, firstLen, secondLen), best(pre, secondLen, firstLen));
    }

    private int best(int[] pre, int leftLen, int rightLen) {
        int n = pre.length - 1;
        int bestLeft = pre[leftLen] - pre[0];
        int ans = 0;

        for (int end = leftLen + rightLen; end <= n; end++) {
            int leftEnd = end - rightLen;
            int leftSum = pre[leftEnd] - pre[leftEnd - leftLen];
            bestLeft = Math.max(bestLeft, leftSum);

            int rightSum = pre[end] - pre[end - rightLen];
            ans = Math.max(ans, bestLeft + rightSum);
        }
        return ans;
    }
}

func maxSumTwoNoOverlap(nums []int, firstLen int, secondLen int) int {
    n := len(nums)
    pre := make([]int, n+1)
    for i, v := range nums {
        pre[i+1] = pre[i] + v
    }
    a := best(pre, firstLen, secondLen)
    b := best(pre, secondLen, firstLen)
    if a > b {
        return a
    }
    return b
}

func best(pre []int, leftLen, rightLen int) int {
    n := len(pre) - 1
    bestLeft := pre[leftLen] - pre[0]
    ans := 0

    for end := leftLen + rightLen; end <= n; end++ {
        leftEnd := end - rightLen
        leftSum := pre[leftEnd] - pre[leftEnd-leftLen]
        if leftSum > bestLeft {
            bestLeft = leftSum
        }

        rightSum := pre[end] - pre[end-rightLen]
        if bestLeft+rightSum > ans {
            ans = bestLeft + rightSum
        }
    }
    return ans
}

class Solution {
public:
    int maxSumTwoNoOverlap(vector<int>& nums, int firstLen, int secondLen) {
        int n = nums.size();
        vector<int> pre(n + 1, 0);
        for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + nums[i];
        return max(best(pre, firstLen, secondLen), best(pre, secondLen, firstLen));
    }

private:
    int best(const vector<int>& pre, int leftLen, int rightLen) {
        int n = (int)pre.size() - 1;
        int bestLeft = pre[leftLen] - pre[0];
        int ans = 0;

        for (int end = leftLen + rightLen; end <= n; end++) {
            int leftEnd = end - rightLen;
            int leftSum = pre[leftEnd] - pre[leftEnd - leftLen];
            bestLeft = max(bestLeft, leftSum);

            int rightSum = pre[end] - pre[end - rightLen];
            ans = max(ans, bestLeft + rightSum);
        }
        return ans;
    }
};

class Solution:
    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:
        pre = [0]
        for v in nums:
            pre.append(pre[-1] + v)

        return max(self.best(pre, firstLen, secondLen),
                   self.best(pre, secondLen, firstLen))

    def best(self, pre: List[int], left_len: int, right_len: int) -> int:
        n = len(pre) - 1
        best_left = pre[left_len] - pre[0]
        ans = 0

        for end in range(left_len + right_len, n + 1):
            left_end = end - right_len
            left_sum = pre[left_end] - pre[left_end - left_len]
            best_left = max(best_left, left_sum)

            right_sum = pre[end] - pre[end - right_len]
            ans = max(ans, best_left + right_sum)

        return ans

/**
 * @param {number[]} nums
 * @param {number} firstLen
 * @param {number} secondLen
 * @return {number}
 */
var maxSumTwoNoOverlap = function(nums, firstLen, secondLen) {
  const n = nums.length;
  const pre = Array(n + 1).fill(0);
  for (let i = 0; i < n; i++) pre[i + 1] = pre[i] + nums[i];

  return Math.max(best(pre, firstLen, secondLen), best(pre, secondLen, firstLen));
};

function best(pre, leftLen, rightLen) {
  const n = pre.length - 1;
  let bestLeft = pre[leftLen] - pre[0];
  let ans = 0;

  for (let end = leftLen + rightLen; end <= n; end++) {
    const leftEnd = end - rightLen;
    const leftSum = pre[leftEnd] - pre[leftEnd - leftLen];
    bestLeft = Math.max(bestLeft, leftSum);

    const rightSum = pre[end] - pre[end - rightLen];
    ans = Math.max(ans, bestLeft + rightSum);
  }
  return ans;
}