让我们走向子数组累加和的世界 本文测试链接:
什么是子数组累加和
子数组累加和(Subarray Sum), 其核心思想是通过将原问题分解为一系列重叠的子问题，逐步解决这些子问题并存储其结果，以避免重复计算, 提升算法效率, 本质是一种用空间换时间的算法思想, 在解决问题中其也会使用到动态规划(Dynamic Programming，简称 DP)的思想, 经常通过前缀和(Prefix Sum)和后缀和(suffix Sum)技巧来高效计算。
实现普通子数组累加和
其主要通过dp的思想来实现, 其主要有两种实现方式 (测试链接: https://leetcode.cn/problems/maximum-subarray/):
- 普通dp实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
class Solution { public: vector<int> dp; int maxSubArray(vector<int>& nums) { int n = nums.size(); dp = vector<int>(n, 0); //1 <= nums.length <= 105 dp[0] = nums[0]; int ans = dp[0]; for (int i = 1; i < n; ++i) { dp[i] = max(nums[i], dp[i - 1] + nums[i]); ans = max(ans, dp[i]); } return ans; } };
解析:
- 其nums.length >= 1, 因此可以省去对应的边界判断。
- dp[0] = nums[0] 初始化, 使后面i = 1开始, 使得后面dp[i - 1]不会越界。
- 在dp的过程中, 同时记录最大值, 防止最后再遍历一遍dp数组。
- ans初始化为dp[0], 是为了防止nums中只有一个元素或取包含nums[0]最大的情况。
点评: 但时间复杂度已经通过dp优化到了O(n), 但是空间复杂度为O(n), 可以进一步优化。
- 空间优化的dp实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
// 空间压缩 class Solution { public: int pre; // 1 <= nums.length <= 105 int maxSubArray(vector<int>& nums) { int n = nums.size(); pre = nums[0]; int ans = nums[0]; for (int i = 1; i < n; ++i) { pre = max(nums[i], pre + nums[i]); ans = max(ans, pre); } return ans; } };
解析:
- 使用pre代替dp数组记录dp[i - 1], 空间复杂度优化到了O(1)。
点评:其空间复杂度已经优化到了O(1), 其时间复杂度也优化到了O(n), 其实现思路是最优的。
实现非环形子数组累加和
其也主要通过dp思想来实现: (测试链接: https://leetcode.cn/problems/house-robber/):
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
#include<algorithm>
class Solution {
public:
vector<int> dp;
int rob(vector<int>& nums) {
int n = nums.size();
// 单独判断情况
if (n == 1)
{
return nums[0];
}
if (n == 2)
{
return max(nums[0], nums[1]);
}
// dp初始化
dp = vector<int>(n, 0);
dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]);
// 主要逻辑
for (int i = 2; i < n; ++i)
{
dp[i] = max(dp[i - 1], max(dp[i], dp[i - 2] + nums[i]));
}
return dp[n - 1];
}
};
解析:
- 单独判断
dp[1] = max(nums[0], nums[1]), 处理打劫1号屋子与2号屋子的情况。 - 使用
dp[i] = max(dp[i - 1], max(dp[i], dp[i - 2] + nums[i]))判断打劫第i号房子和不打劫i号房子的最大情况, 取其中最大值为当前最大值。
实现环形子数组累加和
测试链接: https://leetcode.cn/problems/maximum-sum-circular-subarray/ 这道题存在两种情况:
- 最大数组中间, 直接使用普通的子数组累加和找最大值即可。
- 最大数组在需要数组首尾都包含, 则需要使用全部值的和减去中间最小的子数组累加和即为最大值。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
#include<climits> #include<algorithm> class Solution { public: int maxSubarraySumCircular(vector<int>& nums) { int n = nums.size(); int all = nums[0]; int maxSum = nums[0]; int minSum = nums[0]; for (int i = 1, maxPre = nums[0], minPre = nums[0]; i < n; ++i) { all += nums[i]; maxPre = max(nums[i], maxPre + nums[i]); // 选最大的时候 maxSum = max(maxSum, maxPre); minPre = min(nums[i], minPre + nums[i]); // 选最小的时候 minSum = min(minSum, minPre); } return all == minSum ? maxSum : max(maxSum, all - minSum); // all == minSum : 全部都是为负数, 但不能为空数组就只能返回maxSum } };
解析: *
all - minSum为需要取数组首尾的情况,maxSum为不需要取数组首尾的情况。 *all == minSum为全部都是为负数的情况, 但返回值不能为空数组就只能返回maxSum。
使用前缀和后缀和实现子数组累加和
这一部分我认为是比较难理解的, 其主要用于需要分段子数组累加和最大的问题。 测试链接: https://leetcode.cn/problems/maximum-sum-of-3-non-overlapping-subarrays/
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
class Solution {
public:
vector<int> sums; // 以i位置开头往后k次的累加和
vector<int> prefix;
vector<int> suffix;
vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {
int n = nums.size();
sums = vector<int>(n);
for (int l = 0, r = 0, sum = 0; r < n; ++r)
{
sum += nums[r];
if (r - l + 1 == k)
{
sums[l] = sum;
sum -= nums[l++];
}
}
// prefix : 0 ~ i 的子数组累加和最大值的索引
prefix = vector<int>(n, 0);
prefix[0] = 0;
for (int l = 1, r = k; r < n; ++l, ++r)
{
if (sums[l] > sums[prefix[r - 1]]) // 如果当前位置比之前的位置的子数组累加和数组的值大
{
prefix[r] = l;
}else{
prefix[r] = prefix[r - 1];
}
}
// suffix : i ~ n - 1 的子数组累加和最大值的索引, 索引值为尾部的索引
suffix = vector<int>(n);
suffix[n - k] = n - k;
for (int l = n - 1 - k; l >= 0; --l)
{
if (sums[l] >= sums[suffix[l + 1]]) // 注意这里是>=, 题目要求因为如果有多个结果，返回字典序最小的一个。
{
suffix[l] = l;
}else{
suffix[l] = suffix[l + 1];
}
}
int a, b, c, maxVal = 0;
for (int p, s, i = k, j = 2 * k - 1, sum; j < n - k; ++i, ++j)
{
p = prefix[i - 1];
s = suffix[j + 1];
sum = sums[p] + sums[i] + sums[s];
if (sum > maxVal)
{
a = p;
b = i;
c = s;
maxVal = sum;
}
}
return {a, b, c};
}
};
解析:
- 使用了前缀和后缀和记录起始值的dp思想, 如果来到i位置, 则需要找到
0 ~ i - 1的子数组累加和最大值的索引, 以及i + k ~ n - 1的子数组累加和最大值的索引, 这样情况下使用sum = sums[p] + sums[i] + sums[s];找到三个子数组累加和的最大值。 - 注意这里使用了
>=的判断, 因为如果有多个结果, 则返回字典序最小的一个。
点评: 时间复杂都为O(n), 可以说是一种非常好的实现方式。
总结
- 子数组累加和的核心思想是通过将原问题分解为一系列重叠的子问题，逐步解决这些子问题并存储其结果，以避免重复计算, 提升算法效率, 本质是一种用
空间换时间的算法思想。 - 在解决问题中其也会使用到
动态规划(Dynamic Programming，简称 DP)的思想, 经常通过前缀和(Prefix Sum)和后缀和(suffix Sum)技巧来高效计算。 - 使用前缀和后缀和存储索引的方式实现子数组累加和是一种比较难理解的实现方式, 其主要用于需要分段子数组累加和最大的问题。
