🌐 中文 English
Let’s step into the world of subarray sum Test links for this article:
What is Subarray Sum
Subarray Sum, its core idea is to decompose the original problem into a series of overlapping subproblems, solve these subproblems step by step and store their results to avoid repeated calculations and improve algorithm efficiency. It is essentially an algorithmic idea of trading space for time. In solving problems, it also utilizes the idea of Dynamic Programming (DP for short), often employing techniques like Prefix Sum and Suffix Sum for efficient computation.
Implementing Ordinary Subarray Sum
It is mainly implemented using the DP idea, with two main implementation methods (Test link: https://leetcode.cn/problems/maximum-subarray/):
- Ordinary DP implementation
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; } };
Explanation:
- Since nums.length >= 1, corresponding boundary checks can be omitted.
- dp[0] = nums[0] is initialized, so starting from i = 1, dp[i - 1] will not go out of bounds.
- During the DP process, the maximum value is recorded simultaneously to prevent having to traverse the dp array again at the end.
- ans is initialized to dp[0] to handle cases where nums has only one element or the maximum case includes nums[0].
Comment: The time complexity has been optimized to O(n) through DP, but the space complexity is O(n), which can be further optimized.
- Space-optimized DP implementation
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
// Space compression 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; } };
Explanation:
- Using pre to replace the dp array for recording dp[i - 1], space complexity is optimized to O(1).
Comment: Its space complexity has been optimized to O(1), and its time complexity is also optimized to O(n). This implementation approach is optimal.
Implementing Non-Circular Subarray Sum
It is also mainly implemented using the DP idea: (Test link: 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();
// Handle special cases separately
if (n == 1)
{
return nums[0];
}
if (n == 2)
{
return max(nums[0], nums[1]);
}
// dp initialization
dp = vector<int>(n, 0);
dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]);
// Main logic
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];
}
};
Explanation:
- The separate judgment
dp[1] = max(nums[0], nums[1])handles the cases of robbing house 1 and house 2. - Using
dp[i] = max(dp[i - 1], max(dp[i], dp[i - 2] + nums[i]))determines the maximum between robbing house i and not robbing house i, taking the maximum of these as the current maximum.
Implementing Circular Subarray Sum
Test link: https://leetcode.cn/problems/maximum-sum-circular-subarray/ This problem has two scenarios:
- The maximum subarray is in the middle. Simply use the ordinary subarray sum to find the maximum.
- The maximum subarray includes both the head and tail of the array. Then, the total sum minus the minimum subarray sum in the middle gives the maximum.
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]); // When selecting the maximum maxSum = max(maxSum, maxPre); minPre = min(nums[i], minPre + nums[i]); // When selecting the minimum minSum = min(minSum, minPre); } return all == minSum ? maxSum : max(maxSum, all - minSum); // all == minSum : All numbers are negative, but the return cannot be an empty array, so only maxSum can be returned. } };
Explanation: *
all - minSumis for the case where the array head and tail need to be taken,maxSumis for the case where they don’t. *all == minSumis the case where all numbers are negative, but the return value cannot be an empty array, so onlymaxSumis returned.
Implementing Subarray Sum Using Prefix and Suffix Sums
This part I find relatively difficult to understand. It is mainly used for problems requiring the maximum sum of segmented subarrays. Test link: 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; // The cumulative sum starting from position i for the next k elements
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 : The index of the maximum subarray sum from 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]]) // If the value at the current position's subarray sum array is greater than the previous position's
{
prefix[r] = l;
}else{
prefix[r] = prefix[r - 1];
}
}
// suffix : The index of the maximum subarray sum from i ~ n - 1, the index value is the ending index
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]]) // Note it's >= here, because if there are multiple results, return the lexicographically smallest one.
{
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};
}
};
Explanation:
- It uses the DP idea of recording starting indices with prefix and suffix sums. When arriving at position i, it needs to find the index of the maximum subarray sum from
0 ~ i - 1, and the index of the maximum subarray sum fromi + k ~ n - 1. In this scenario, usingsum = sums[p] + sums[i] + sums[s];finds the maximum sum of three subarrays. - Note the use of
>=in the judgment here, because if there are multiple results, the lexicographically smallest one should be returned.
Comment: The time complexity is O(n), which can be considered a very good implementation.
Summary
- The core idea of subarray sum is to decompose the original problem into a series of overlapping subproblems, solve these subproblems step by step and store their results to avoid repeated calculations and improve algorithm efficiency. It is essentially an algorithmic idea of
trading space for time. - In solving problems, it also utilizes the idea of
Dynamic Programming(DP for short), often employing techniques likePrefix SumandSuffix Sumfor efficient computation. - Implementing subarray sum using prefix and suffix sums to store indices is a relatively difficult-to-understand implementation method. It is mainly used for problems requiring the maximum sum of segmented subarrays.
