LeetCode 689. 三个无重叠子数组的最大和

Categories:

题目描述
思路分析
1. 解法一：滑动窗口 + 预计算前缀最优（推荐）
相似题目

题目描述

✅ 689. 三个无重叠子数组的最大和

思路分析

解法一：滑动窗口 + 预计算前缀最优（推荐）

核心思路：

先用滑动窗口计算每个起始位置长度为 k 的子数组之和，存入 sums 数组

预计算 left[i]：从左到 i 位置，子数组和最大的起始下标（相等时取左边）

预计算 right[i]：从右到 i 位置，子数组和最大的起始下标（相等时取右边）

枚举中间子数组的起始位置 j（从 k 到 n-2k），结合 left[j-1] 和 right[j+k]，更新最大和

复杂度分析：

时间复杂度：O(n)，其中 n 表示数组长度，三次线性扫描

空间复杂度：O(n)，其中 n 为数组长度，用于存储 sums、left、right 数组

class Solution {
    public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
        int n = nums.length;
        int[] sums = new int[n - k + 1];

        // 计算每个起始位置长度为 k 的子数组之和
        int windowSum = 0;
        for (int i = 0; i < k; i++) {
            windowSum += nums[i];
        }
        sums[0] = windowSum;
        for (int i = 1; i <= n - k; i++) {
            windowSum += nums[i + k - 1] - nums[i - 1];
            sums[i] = windowSum;
        }

        // left[i]：[0, i] 中子数组和最大的起始下标
        int[] left = new int[sums.length];
        int bestLeft = 0;
        for (int i = 0; i < sums.length; i++) {
            if (sums[i] > sums[bestLeft]) {
                bestLeft = i;
            }
            left[i] = bestLeft;
        }

        // right[i]：[i, n-k] 中子数组和最大的起始下标
        int[] right = new int[sums.length];
        int bestRight = sums.length - 1;
        for (int i = sums.length - 1; i >= 0; i--) {
            if (sums[i] >= sums[bestRight]) {
                bestRight = i;
            }
            right[i] = bestRight;
        }

        // 枚举中间子数组，结合左右最优起始位置求最大和
        int[] result = new int[]{-1, -1, -1};
        int maxSum = 0;
        for (int j = k; j <= n - 2 * k; j++) {
            int l = left[j - 1];
            int r = right[j + k];
            int total = sums[l] + sums[j] + sums[r];

            if (total > maxSum) {
                maxSum = total;
                result[0] = l;
                result[1] = j;
                result[2] = r;
            }
        }

        return result;
    }
}

func maxSumOfThreeSubarrays(nums []int, k int) []int {
    n := len(nums)
    sums := make([]int, n-k+1)

    // 计算每个起始位置长度为 k 的子数组之和
    windowSum := 0
    for i := 0; i < k; i++ {
        windowSum += nums[i]
    }
    sums[0] = windowSum
    for i := 1; i <= n-k; i++ {
        windowSum += nums[i+k-1] - nums[i-1]
        sums[i] = windowSum
    }

    // left[i]：[0, i] 中子数组和最大的起始下标
    left := make([]int, len(sums))
    bestLeft := 0
    for i := 0; i < len(sums); i++ {
        if sums[i] > sums[bestLeft] {
            bestLeft = i
        }
        left[i] = bestLeft
    }

    // right[i]：[i, n-k] 中子数组和最大的起始下标
    right := make([]int, len(sums))
    bestRight := len(sums) - 1
    for i := len(sums) - 1; i >= 0; i-- {
        if sums[i] >= sums[bestRight] {
            bestRight = i
        }
        right[i] = bestRight
    }

    // 枚举中间子数组，结合左右最优起始位置求最大和
    result := []int{-1, -1, -1}
    maxSum := 0
    for j := k; j <= n-2*k; j++ {
        l := left[j-1]
        r := right[j+k]
        total := sums[l] + sums[j] + sums[r]

        if total > maxSum {
            maxSum = total
            result[0] = l
            result[1] = j
            result[2] = r
        }
    }

    return result
}

相似题目

题目	难度	考察点
123. 买卖股票的最佳时机 III	困难	动态规划、预计算
188. 买卖股票的最佳时机 IV	困难	动态规划
53. 最大子数组和	中等	动态规划、前缀和
209. 长度最小的子数组	中等	滑动窗口
643. 子数组最大平均数 I	简单	滑动窗口
1031. 两个非重叠子数组的最大和	中等	滑动窗口、预计算

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2021/11776921