0689-三个无重叠子数组的最大和

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:27 2023-09-13 16:06:27 Updated    

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

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

示例 1：

**输入：** nums = [1,2,1,2,6,7,5,1], k = 2
**输出：** [0,3,5]
**解释：** 子数组 [1, 2], [2, 6], [7, 5] 对应的起始下标为 [0, 3, 5]。
也可以取 [2, 1], 但是结果 [1, 3, 5] 在字典序上更大。

示例 2：

**输入：** nums = [1,2,1,2,1,2,1,2,1], k = 2
**输出：** [0,2,4]

提示：

  • 1 <= nums.length <= 2 * 104
  • 1 <= nums[i] < 216
  • 1 <= k <= floor(nums.length / 3)

要计算三个无重叠子数组的最大和，我们可以枚举第三个子数组的位置，同时维护前两个无重叠子数组的最大和及其位置。

要计算两个无重叠子数组的最大和，我们可以枚举第二个子数组的位置，同时维护第一个子数组的最大和及其位置。

因此，我们首先来解决单个子数组的最大和问题，然后解决两个无重叠子数组的最大和问题，最后解决三个无重叠子数组的最大和问题。

前言一：单个子数组的最大和

我们用滑动窗口来解决这一问题。

滑动窗口是数组/字符串问题中常用的抽象概念。窗口通常是指在数组/字符串中由开始和结束索引定义的一系列元素的集合，即闭区间 [i,j]。而滑动窗口是指可以将两个边界向某一方向「滑动」的窗口。例如，我们将 [i,j] 向右滑动 1 个元素，它将变为 [i+1,j+1]。

设 sum}_1 为大小为 k 的窗口的元素和，当窗口从 [i-k+1,i] 向右滑动 1 个元素后，sum}_1 增加了 nums}[i+1]，减少了 nums}[i-k+1]。据此我们可以 O(1) 地计算出向右滑动 1 个元素后的窗口的元素和。

我们从 [0,k-1] 开始，不断地向右滑动窗口，直至窗口右端点到达数组末尾时停止。统计这一过程中的 sum}_1 的最大值（记作 maxSum}_1）及其对应位置。

[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def maxSumOfOneSubarray(self, nums: List[int], k: int) -> List[int]:
        ans = []
        sum1, maxSum1 = 0, 0
        for i, num in enumerate(nums):
            sum1 += num
            if i >= k - 1:
                if sum1 > maxSum1:
                    maxSum1 = sum1
                    ans = [i - k + 1]
                sum1 -= nums[i - k + 1]
        return ans
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> maxSumOfOneSubarray(vector<int> &nums, int k) {
        vector<int> ans;
        int sum1 = 0, maxSum1 = 0;
        for (int i = 0; i < nums.size(); ++i) {
            sum1 += nums[i];
            if (i >= k - 1) {
                if (sum1 > maxSum1) {
                    maxSum1 = sum1;
                    ans = {i - k + 1};
                }
                sum1 -= nums[i - k + 1];
            }
        }
        return ans;
    }
};
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int[] maxSumOfOneSubarray(int[] nums, int k) {
        int[] ans = new int[1];
        int sum1 = 0, maxSum1 = 0;
        for (int i = 0; i < nums.length; ++i) {
            sum1 += nums[i];
            if (i >= k - 1) {
                if (sum1 > maxSum1) {
                    maxSum1 = sum1;
                    ans[0] = i - k + 1;
                }
                sum1 -= nums[i - k + 1];
            }
        }
        return ans;
    }
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
    public int[] MaxSumOfOneSubarray(int[] nums, int k) {
        int[] ans = new int[1];
        int sum1 = 0, maxSum1 = 0;
        for (int i = 0; i < nums.Length; ++i) {
            sum1 += nums[i];
            if (i >= k - 1) {
                if (sum1 > maxSum1) {
                    maxSum1 = sum1;
                    ans[0] = i - k + 1;
                }
                sum1 -= nums[i - k + 1];
            }
        }
        return ans;
    }
}
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
func maxSumOfOneSubarray(nums []int, k int) (ans []int) {
    var sum1, maxSum1 int
    for i, num := range nums {
        sum1 += num
        if i >= k-1 {
            if sum1 > maxSum1 {
                maxSum1 = sum1
                ans = []int{i - k + 1}
            }
            sum1 -= nums[i-k+1]
        }
    }
    return
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var maxSumOfOneSubarray = function(nums, k) {
    let ans = [];
    let sum1 = 0, maxSum1 = 0;
    for (let i = 0; i < nums.length; ++i) {
        sum1 += nums[i];
        if (i >= k - 1) {
            if (sum1 > maxSum1) {
                maxSum1 = sum1;
                ans = [i - k + 1];
            }
            sum1 -= nums[i - k + 1];
        }
    }
    return ans;
};

前言二：两个无重叠子数组的最大和

我们使用两个大小为 k 的滑动窗口。设 sum}_1 为第一个滑动窗口的元素和，该滑动窗口从 [0,k-1] 开始；sum}_2 为第二个滑动窗口的元素和，该滑动窗口从 [k,2k-1] 开始。

我们同时向右滑动这两个窗口，并维护 sum}_1 的最大值 maxSum}_1 及其对应位置。每次滑动时，计算当前 maxSum}_1 与 sum}_2 之和。统计这一过程中的 maxSum}_1+\textit{sum}2 的最大值（记作 maxSum}{12）及其对应位置。

[sol2-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def maxSumOfTwoSubarrays(self, nums: List[int], k: int) -> List[int]:
        ans = []
        sum1, maxSum1, maxSum1Idx = 0, 0, 0
        sum2, maxSum12 = 0, 0
        for i in range(k, len(nums)):
            sum1 += nums[i - k]
            sum2 += nums[i]
            if i >= k * 2 - 1:
                if sum1 > maxSum1:
                    maxSum1 = sum1
                    maxSum1Idx = i - k * 2 + 1
                if maxSum1 + sum2 > maxSum12:
                    maxSum12 = maxSum1 + sum2
                    ans = [maxSum1Idx, i - k + 1]
                sum1 -= nums[i - k * 2 + 1]
                sum2 -= nums[i - k + 1]
        return ans
[sol2-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    vector<int> maxSumOfTwoSubarrays(vector<int> &nums, int k) {
        vector<int> ans;
        int sum1 = 0, maxSum1 = 0, maxSum1Idx = 0;
        int sum2 = 0, maxSum12 = 0;
        for (int i = k; i < nums.size(); ++i) {
            sum1 += nums[i - k];
            sum2 += nums[i];
            if (i >= k * 2 - 1) {
                if (sum1 > maxSum1) {
                    maxSum1 = sum1;
                    maxSum1Idx = i - k * 2 + 1;
                }
                if (maxSum1 + sum2 > maxSum12) {
                    maxSum12 = maxSum1 + sum2;
                    ans = {maxSum1Idx, i - k + 1};
                }
                sum1 -= nums[i - k * 2 + 1];
                sum2 -= nums[i - k + 1];
            }
        }
        return ans;
    }
};
[sol2-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int[] maxSumOfTwoSubarrays(int[] nums, int k) {
        int[] ans = new int[2];
        int sum1 = 0, maxSum1 = 0, maxSum1Idx = 0;
        int sum2 = 0, maxSum12 = 0;
        for (int i = k; i < nums.length; ++i) {
            sum1 += nums[i - k];
            sum2 += nums[i];
            if (i >= k * 2 - 1) {
                if (sum1 > maxSum1) {
                    maxSum1 = sum1;
                    maxSum1Idx = i - k * 2 + 1;
                }
                if (maxSum1 + sum2 > maxSum12) {
                    maxSum12 = maxSum1 + sum2;
                    ans[0] = maxSum1Idx;
                    ans[1] = i - k + 1;
                }
                sum1 -= nums[i - k * 2 + 1];
                sum2 -= nums[i - k + 1];
            }
        }
        return ans;
    }
}
[sol2-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class Solution {
    public int[] MaxSumOfTwoSubarrays(int[] nums, int k) {
        int[] ans = new int[2];
        int sum1 = 0, maxSum1 = 0, maxSum1Idx = 0;
        int sum2 = 0, maxSum12 = 0;
        for (int i = k; i < nums.Length; ++i) {
            sum1 += nums[i - k];
            sum2 += nums[i];
            if (i >= k * 2 - 1) {
                if (sum1 > maxSum1) {
                    maxSum1 = sum1;
                    maxSum1Idx = i - k * 2 + 1;
                }
                if (maxSum1 + sum2 > maxSum12) {
                    maxSum12 = maxSum1 + sum2;
                    ans[0] = maxSum1Idx;
                    ans[1] = i - k + 1;
                }
                sum1 -= nums[i - k * 2 + 1];
                sum2 -= nums[i - k + 1];
            }
        }
        return ans;
    }
}
[sol2-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func maxSumOfTwoSubarrays(nums []int, k int) (ans []int) {
    var sum1, maxSum1, maxSum1Idx int
    var sum2, maxSum12 int
    for i := k; i < len(nums); i++ {
        sum1 += nums[i-k]
        sum2 += nums[i]
        if i >= k*2-1 {
            if sum1 > maxSum1 {
                maxSum1 = sum1
                maxSum1Idx = i - k*2 + 1
            }
            if maxSum1+sum2 > maxSum12 {
                maxSum12 = maxSum1 + sum2
                ans = []int{maxSum1Idx, i - k + 1}
            }
            sum1 -= nums[i-k*2+1]
            sum2 -= nums[i-k+1]
        }
    }
    return
}
[sol2-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
const maxSumOfTwoSubarrays = (nums, k) => {
    const ans = [0, 0];
    let sum1 = 0, maxSum1 = 0, maxSum1Idx = 0;
    let sum2 = 0, maxSum12 = 0;
    for (let i = k; i < nums.length; ++i) {
        sum1 += nums[i - k];
        sum2 += nums[i];
        if (i >= k * 2 - 1) {
            if (sum1 > maxSum1) {
                maxSum1 = sum1;
                maxSum1Idx = i - k * 2 + 1;
            }
            if (maxSum1 + sum2 > maxSum12) {
                maxSum12 = maxSum1 + sum2;
                ans[0] = maxSum1Idx;
                ans[1] = i - k + 1;
            }
            sum1 -= nums[i - k * 2 + 1];
            sum2 -= nums[i - k + 1];
        }
    }
    return ans;
}

方法一：滑动窗口

回到本题，我们使用三个大小为 k 的滑动窗口。设 sum}_1 为第一个滑动窗口的元素和，该滑动窗口从 [0,k-1] 开始；sum}_2 为第二个滑动窗口的元素和，该滑动窗口从 [k,2k-1] 开始；sum}_3 为第三个滑动窗口的元素和，该滑动窗口从 [2k,3k-1] 开始。

我们同时向右滑动这三个窗口，按照前言二的方法并维护 maxSum}{12 及其对应位置。每次滑动时，计算当前 maxSum}{12 与 sum}3 之和。统计这一过程中的 maxSum}{12}+\textit{sum}_3 的最大值及其对应位置。

对于题目要求的最小字典序，由于我们是从左向右遍历的，并且仅当元素和超过最大元素和时才修改最大元素和，从而保证求出来的下标列表是字典序最小的。

[sol3-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:
        ans = []
        sum1, maxSum1, maxSum1Idx = 0, 0, 0
        sum2, maxSum12, maxSum12Idx = 0, 0, ()
        sum3, maxTotal = 0, 0
        for i in range(k * 2, len(nums)):
            sum1 += nums[i - k * 2]
            sum2 += nums[i - k]
            sum3 += nums[i]
            if i >= k * 3 - 1:
                if sum1 > maxSum1:
                    maxSum1 = sum1
                    maxSum1Idx = i - k * 3 + 1
                if maxSum1 + sum2 > maxSum12:
                    maxSum12 = maxSum1 + sum2
                    maxSum12Idx = (maxSum1Idx, i - k * 2 + 1)
                if maxSum12 + sum3 > maxTotal:
                    maxTotal = maxSum12 + sum3
                    ans = [*maxSum12Idx, i - k + 1]
                sum1 -= nums[i - k * 3 + 1]
                sum2 -= nums[i - k * 2 + 1]
                sum3 -= nums[i - k + 1]
        return ans
[sol3-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    vector<int> maxSumOfThreeSubarrays(vector<int> &nums, int k) {
        vector<int> ans;
        int sum1 = 0, maxSum1 = 0, maxSum1Idx = 0;
        int sum2 = 0, maxSum12 = 0, maxSum12Idx1 = 0, maxSum12Idx2 = 0;
        int sum3 = 0, maxTotal = 0;
        for (int i = k * 2; i < nums.size(); ++i) {
            sum1 += nums[i - k * 2];
            sum2 += nums[i - k];
            sum3 += nums[i];
            if (i >= k * 3 - 1) {
                if (sum1 > maxSum1) {
                    maxSum1 = sum1;
                    maxSum1Idx = i - k * 3 + 1;
                }
                if (maxSum1 + sum2 > maxSum12) {
                    maxSum12 = maxSum1 + sum2;
                    maxSum12Idx1 = maxSum1Idx;
                    maxSum12Idx2 = i - k * 2 + 1;
                }
                if (maxSum12 + sum3 > maxTotal) {
                    maxTotal = maxSum12 + sum3;
                    ans = {maxSum12Idx1, maxSum12Idx2, i - k + 1};
                }
                sum1 -= nums[i - k * 3 + 1];
                sum2 -= nums[i - k * 2 + 1];
                sum3 -= nums[i - k + 1];
            }
        }
        return ans;
    }
};
[sol3-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
        int[] ans = new int[3];
        int sum1 = 0, maxSum1 = 0, maxSum1Idx = 0;
        int sum2 = 0, maxSum12 = 0, maxSum12Idx1 = 0, maxSum12Idx2 = 0;
        int sum3 = 0, maxTotal = 0;
        for (int i = k * 2; i < nums.length; ++i) {
            sum1 += nums[i - k * 2];
            sum2 += nums[i - k];
            sum3 += nums[i];
            if (i >= k * 3 - 1) {
                if (sum1 > maxSum1) {
                    maxSum1 = sum1;
                    maxSum1Idx = i - k * 3 + 1;
                }
                if (maxSum1 + sum2 > maxSum12) {
                    maxSum12 = maxSum1 + sum2;
                    maxSum12Idx1 = maxSum1Idx;
                    maxSum12Idx2 = i - k * 2 + 1;
                }
                if (maxSum12 + sum3 > maxTotal) {
                    maxTotal = maxSum12 + sum3;
                    ans[0] = maxSum12Idx1;
                    ans[1] = maxSum12Idx2;
                    ans[2] = i - k + 1;
                }
                sum1 -= nums[i - k * 3 + 1];
                sum2 -= nums[i - k * 2 + 1];
                sum3 -= nums[i - k + 1];
            }
        }
        return ans;
    }
}
[sol3-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public class Solution {
    public int[] MaxSumOfThreeSubarrays(int[] nums, int k) {
        int[] ans = new int[3];
        int sum1 = 0, maxSum1 = 0, maxSum1Idx = 0;
        int sum2 = 0, maxSum12 = 0, maxSum12Idx1 = 0, maxSum12Idx2 = 0;
        int sum3 = 0, maxTotal = 0;
        for (int i = k * 2; i < nums.Length; ++i) {
            sum1 += nums[i - k * 2];
            sum2 += nums[i - k];
            sum3 += nums[i];
            if (i >= k * 3 - 1) {
                if (sum1 > maxSum1) {
                    maxSum1 = sum1;
                    maxSum1Idx = i - k * 3 + 1;
                }
                if (maxSum1 + sum2 > maxSum12) {
                    maxSum12 = maxSum1 + sum2;
                    maxSum12Idx1 = maxSum1Idx;
                    maxSum12Idx2 = i - k * 2 + 1;
                }
                if (maxSum12 + sum3 > maxTotal) {
                    maxTotal = maxSum12 + sum3;
                    ans[0] = maxSum12Idx1;
                    ans[1] = maxSum12Idx2;
                    ans[2] = i - k + 1;
                }
                sum1 -= nums[i - k * 3 + 1];
                sum2 -= nums[i - k * 2 + 1];
                sum3 -= nums[i - k + 1];
            }
        }
        return ans;
    }
}
[sol3-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
func maxSumOfThreeSubarrays(nums []int, k int) (ans []int) {
    var sum1, maxSum1, maxSum1Idx int
    var sum2, maxSum12, maxSum12Idx1, maxSum12Idx2 int
    var sum3, maxTotal int
    for i := k * 2; i < len(nums); i++ {
        sum1 += nums[i-k*2]
        sum2 += nums[i-k]
        sum3 += nums[i]
        if i >= k*3-1 {
            if sum1 > maxSum1 {
                maxSum1 = sum1
                maxSum1Idx = i - k*3 + 1
            }
            if maxSum1+sum2 > maxSum12 {
                maxSum12 = maxSum1 + sum2
                maxSum12Idx1, maxSum12Idx2 = maxSum1Idx, i-k*2+1
            }
            if maxSum12+sum3 > maxTotal {
                maxTotal = maxSum12 + sum3
                ans = []int{maxSum12Idx1, maxSum12Idx2, i - k + 1}
            }
            sum1 -= nums[i-k*3+1]
            sum2 -= nums[i-k*2+1]
            sum3 -= nums[i-k+1]
        }
    }
    return
}
[sol3-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
const maxSumOfThreeSubarrays = (nums, k) => {
    const ans = [0, 0, 0];
    let sum1 = 0, maxSum1 = 0, maxSum1Idx = 0;
    let sum2 = 0, maxSum12 = 0, maxSum12Idx1 = 0, maxSum12Idx2 = 0;
    let sum3 = 0, maxTotal = 0;
    for (let i = k * 2; i < nums.length; ++i) {
        sum1 += nums[i - k * 2];
        sum2 += nums[i - k];
        sum3 += nums[i];
        if (i >= k * 3 - 1) {
            if (sum1 > maxSum1) {
                maxSum1 = sum1;
                maxSum1Idx = i - k * 3 + 1;
            }
            if (maxSum1 + sum2 > maxSum12) {
                maxSum12 = maxSum1 + sum2;
                maxSum12Idx1 = maxSum1Idx;
                maxSum12Idx2 = i - k * 2 + 1;
            }
            if (maxSum12 + sum3 > maxTotal) {
                maxTotal = maxSum12 + sum3;
                ans[0] = maxSum12Idx1;
                ans[1] = maxSum12Idx2;
                ans[2] = i - k + 1;
            }
            sum1 -= nums[i - k * 3 + 1];
            sum2 -= nums[i - k * 2 + 1];
            sum3 -= nums[i - k + 1];
        }
    }
    return ans;
}

复杂度分析

  • 时间复杂度：O(n)，其中 n 是数组 nums 的长度。

  • 空间复杂度：O(1)。我们只需要常数空间来存放若干变量。

结语

此题也可以用动态规划求解，总体思路是我们用 dp}[i][j]​ 表示到数组第 j​ 个元素为止，前 i​ 个互不重叠的子数组的最大值。对于当前第 j​ 个元素所对应的值，我们有不取和取两种选择，选择不取该元素，则值为到 j-1​ 个元素时前 i​ 个互不重叠的子数组的最大值，即 dp}[i][j-1]​ ，选择取该元素，则值为到 j-k​ 个元素时前 i-1​ 个互不重叠的子数组的最大值 dp}[i-1][j-k]​ 加上最后一段子数组的和，我们选择这两种情况下较大值即可，可以得到如下状态转移方程：

\textit{dp}[i][j] =
\max(\textit{dp}[i][j-1],\textit{dp}[i-1][j-k]+\textit{sum}[j]-\textit{sum}[j-k])

其中，sum 为前缀和数组。

感兴趣的读者可以自行尝试。

 Comments
On this page
0689-三个无重叠子数组的最大和