1.题目基本信息

1.1.题目描述

给你一个整数数组 nums 和一个整数 k ，找出三个长度为 k 、互不重叠、且全部数字和最大的子数组，并返回这三个子数组。

以下标的数组形式返回结果，数组中的每一项分别指示每个子数组的起始位置（下标从 0 开始）。如果有多个结果，返回字典序最小的一个。

1.2.题目地址

https://leetcode.cn/problems/maximum-sum-of-3-non-overlapping-subarrays/description/

2.解题方法

2.1.解题思路

滑动窗口 / 动态规划

2.2.解题步骤

思路1：滑动窗口

• 第一步，构建维护变量。假定有连续的三个滑动窗口。sum1维护第一个滑动窗口的数值和，maxSum1维护第一个滑动窗口的最大数值和，maxSum1Idxs维护第一个滑动窗口取得最大值时的起始索引位置；sum2维护第二个滑动窗口的和，maxSum12维护第一个和第二个滑动窗口数值和的最大值，maxSum12Idx维护maxSum12取得时的第一个窗口和第二个窗口的起始索引数组；sum3维护第三个滑动窗口的和，maxTotal维护三个窗口的数值和的最大值；result维护结果数组

• 第二步，遍历数组，更新维护变量，并返回结果

思路2：动态规划

• 第一步，预处理。计算nums的前缀和数组，为了O(1)求子数组的和

• 第二步，状态定义。dp[i][j]表示从nums[i:]中选出j个长度为k、互不重叠、且全部数字和最大的子数组的数值和

• 第三步，状态初始化。dp[][]=0

• 第四步，状态转移。dp[i][j]=max(dp[i+1][j],dp[i+k][j-1]+sum(nums[i:i+k]))

• 第五步，根据dp[0][3]逆向找出无重叠数组的起始索引，根据递推公式进行逆向递推

  • 5.1.构建维护变量。i维护下一个子数组的首指针，j维护还需找的子数组的个数，idx维护当前找的首指针在结果数组中的索引位置；result维护结果数组

3.解题代码

python3代码-滑动窗口

class Solution:
    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:
        # 思路1：滑动窗口
        n = len(nums)
        # 第一步，构建维护变量。假定有连续的三个滑动窗口。sum1维护第一个滑动窗口的数值和，maxSum1维护第一个滑动窗口的最大数值和，maxSum1Idxs维护第一个滑动窗口取得最大值时的起始索引位置；sum2维护第二个滑动窗口的和，maxSum12维护第一个和第二个滑动窗口数值和的最大值，maxSum12Idx维护maxSum12取得时的第一个窗口和第二个窗口的起始索引数组；sum3维护第三个滑动窗口的和，maxTotal维护三个窗口的数值和的最大值；result维护结果数组
        sum1, maxSum1, maxSum1Idx = 0, 0, 0
        sum2, maxSum12, maxSum12Idxs = 0, 0, ()
        sum3, maxTotal = 0, 0
        result = [0, 0, 0]
        # 第二步，遍历数组，更新维护变量，并返回结果
        for i in range(n):
            if i >= k * 3:
                sum1 -= nums[i - 3 * k]
            if i >= k * 2:
                sum1 += nums[i - 2 * k]
                if sum1 > maxSum1:
                    maxSum1 = sum1
                    maxSum1Idx = max(i - 3 * k + 1, 0)
                sum2 -= nums[i - 2 * k]
            if i >= k:
                sum2 += nums[i - k]
                if sum2 + maxSum1 > maxSum12:
                    maxSum12 = sum2 + maxSum1
                    maxSum12Idxs = (maxSum1Idx, max(i - 2 * k + 1, 0))
                sum3 -= nums[i - k]
            sum3 += nums[i]
            if i >= 3 * k - 1:
                if sum3 + maxSum12 > maxTotal:
                    maxTotal = sum3 + maxSum12
                    result = [maxSum12Idxs[0], maxSum12Idxs[1], i - k + 1]
        return result

python3代码-动态规划

class Solution:
    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:
        # 思路2：动态规划
        n = len(nums)
        # 第一步，预处理。计算nums的前缀和数组，为了O(1)求子数组的和
        preSums = [0] * (n + 1)
        for i in range(n):
            preSums[i + 1] = preSums[i] + nums[i]
        # 第二步，状态定义。dp[i][j]表示从nums[i:]中选出j个长度为k、互不重叠、且全部数字和最大的子数组的数值和
        dp = [[0] * 4 for _ in range(n + 1)]
        # 第三步，状态初始化。dp[*][*]=0
        # 第四步，状态转移。dp[i][j]=max(dp[i+1][j],dp[i+k][j-1]+sum(nums[i:i+k]))
        for i in range(n - k, -1, -1):
            for j in range(1, 4):
                if n - i >= k * j:
                    dp[i][j] = max(dp[i + 1][j], dp[i + k][j - 1] + preSums[i + k] - preSums[i])
        # print(dp)
        # 第五步，根据dp[0][3]逆向找出无重叠数组的起始索引，根据递推公式进行逆向递推
        # 5.1.构建维护变量。i维护下一个子数组的首指针，j维护还需找的子数组的个数，idx维护当前找的首指针在结果数组中的索引位置；result维护结果数组
        i, j, idx = 0, 3, 0
        result = [0, 0, 0]
        while j > 0:
            if dp[i][j] > dp[i + k][j - 1] + preSums[i + k] - preSums[i]:
                i += 1
            else:
                # > 取i开头且长度为k的子数组
                result[idx] = i
                i += k
                j -= 1
                idx += 1
        return result

4.执行结果