From subarray problems to Kadane and applications
Let’s start with a problem (src: leetcode#53)
Given an integer array nums, find the subarray with the largest sum, and return its sum.
Constraints:
γ» 1 <= nums.length <= 1e5
γ» -1e4 <= nums[i] <= 1e4
Since subarray means to a contiguous non-empty sequence of elements within an array. It’s easy to find the trivial solution where we try to calculate all possible subarray.
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int ans = INT_MIN;
for (int l = 0; l < nums.size(); ++l) {
for (int r = l; r < nums.size(); ++r) {
int sum = 0;
for (int i = l; i <= r; i++) sum += nums[i];
ans = max(ans, sum);
}
}
return ans;
}
};
The time complexity for this solution is $O(n^{3})$ which clearly impossible to be an AC solution. Then how to update that?
We may notice that the most inner for loop which be used to calculate sum of nums in range [l, r], it can be done better. Due to we only update r => (r+1), then we obviously have
sum(l, r+1) = sum(l, r) + nums[r+1]
The trick is to recognize that all of the subarrays starting at a particular value will share a common prefix. (1)
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int ans = INT_MIN;
for (int l = 0; l < nums.size(); ++l) {
int sum = 0;
for (int r = l; r < nums.size(); ++r) {
sum += nums[r];
ans = max(ans, sum);
}
}
return ans;
}
};
The time complexity for this solution is $O(n^{2})$ and yes it’s still not an AC solution due to the problem constraints.
Back to the previous intuition (1), suppose we have a vector prefix which prefix[i] is sum of all element in nums up to i. Then we obviously have
sum(l, r) = prefix[r] - prefix[l] + nums[l]
or
sum(l, r) = prefix[r] - prefix[l-1]
The prefix[r] is a constant for each iteration at r. That means to maximize the sum(l, r), we have to find the minimum prefix[l-1] or whichever previous MIN.
That can be done using a variable which maintain previous min.
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int sum = 0, ans = nums[0];
int mn = 0; // Min prefix sum[l] at specify r.
for (int &r : nums){
// Prefix up to r.
sum += r;
// Update ans by compare with sum(l+1, r)
// with l provides sum[l] min
ans = max(ans, sum - mn);
// Maintain min by compare with latest prefix
mn = min(mn, sum);
}
return ans;
}
};
The time complexity for this solution is $O(n)$ and yes it’s an AC π
Though we found the $O(n)$ solution for this problem, this question in particular is a popular problem that can be solved using an algorithm called Kadane’s Algorithm.
It is based on a pretty greedy-like intuition: Since the numbers input contains negative numbers that subtract the accumulated sum up to that point, to find the max for a subarray, we have to figure out when a negative number is βworthβ keeping in that subarray.
Obviously, we have: If the accumulated sum up to i is a negative number, then of course it’s better to start over with the accumulated sum reset to 0.
accumulate_sum = max(accumulated_sum, 0)
or
accumulate_sum = max(nums[i+1], accumulated_sum + nums[i+1])
This means we don’t care about any accumulated sum, which contributes a negative sum to the later subarray sum. If an accumulated sum up to the current position is negative, we drop it and start over.
Note: If you think deeply, you may notice the previous solution (maintain previous min) is a more general case for this approach (yes, please take time to think about that).
Then we have the Kadane implementation
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int sum = 0, ans = nums[0];
for (auto num: nums) {
// Kadane intuition!
sum = max(sum, 0) + num;
// Update ans by compare with current accumulated sum
ans = max(ans, sum);
}
return ans;
}
};
And yes, it’s a $O(n)$ solution as well!! Just as good as the min maintaining approach.
So why Kadane?
Since it’s a subset of the general min maintaining approach, it’s easier to implement. You will see what I mean if you think about the title problem but in revert condition, where we want to find minimum subarray.
class Solution {
public:
int minSubArray(vector<int>& nums) {
int sum = 0, ans = nums[0];
for (auto num: nums) {
// Kadane intuition!
sum = min(sum, 0) + num;
// Update ans by compare with current accumulated sum
ans = min(ans, sum);
}
return ans;
}
};
Simply change max to min, and you have the answer π
And, for something that’s more complex like: Maximum Absolute Sum of Any Subarray (ref: leetcode#1749)
class Solution {
public:
// AbsoluteMax = max(max_sum, abs(min_sum))
int maxAbsoluteSum(vector<int>& nums) {
// cur_max is max which stop at current index.
// cur_min is min which stop at current index.
int cur_max = 0, cur_min = 0, max_sum = nums[0], min_sum = nums[0];
for (auto num: nums) {
// Kadane find max sum
cur_max = max(cur_max, 0) + num;
max_sum = max(max_sum, cur_max);
// Kadane find min sum
cur_min = min(cur_min, 0) + num;
min_sum = min(min_sum, cur_min);
}
return max(max_sum, abs(min_sum));
}
};
And Maximum Sum Circular Subarray (ref: leetcode#918)
class Solution {
public:
// The answer will be one of
// - Straight max sum (Kadane max sum)
// - Circular max sum which equal to (array_sum - Kadane min sum)
int maxSubarraySumCircular(vector<int>& nums) {
// cur_max is max which stop at current index.
// cur_min is min which stop at current index.
int cur_max = 0, cur_min = 0, max_sum = nums[0], min_sum = nums[0];
int sum = 0;
for (auto num: nums) {
// Kadane find max sum
cur_max = max(cur_max, 0) + num;
max_sum = max(max_sum, cur_max);
// Kadane find min sum
cur_min = min(cur_min, 0) + num;
min_sum = min(min_sum, cur_min);
// Accumulative sum up all nums elements.
sum += num;
}
// If array sum is a min, then which ever max_sum will be max
// else max would be max_sum or sum - min_sum (circular sum).
return sum == min_sum ? max_sum : max(max_sum, sum - min_sum);
}
};
Note: Try to solve these problems using the “min maintaining approach” by yourself as an exercise.
And yes, you will see how Kadane helps us if you try to solve these problems without the Kadane’s approach π
Take out
For subarray problem, always think about the prefix since every subarray can be calculated based on two prefix.
Also remember the beautiful Kadane algorithm. It for sure will save you someday. Thanks to Kadane π