Description
You are given an integer array nums. The absolute sum of a subarray [s0, s1, ..., sn] is abs(s0 + s1 + ... + sn).
Return the maximum absolute sum of any (possibly empty) subarray of nums.
Solution
We are basically finding the subarray that has the largest sum and the subarray that has the smallest sum. And maximum subarray problem could be solved using dynamic programming, i.e. Kadane’s algorithm. And since we are finding the maximum absolute sum of subarray, we run two Kadane’s algorithm for maximum and minimum sum of subarray.
Kadane’s Algorithm
For an array nums, starting from index 0 to nums.size() - 1, we accumulate the numbers in the array:
The basic idea behind this algorithm is that a local sum that $<0$ will have no use of getting a larger sum for the numbers left in the sequence. Therefore, when ever we get a negative “local maximum sum”, we reset the local sum. If the previous accumulated local sum $>0$, then the sum could contribute, making the sum larger for the coming number in the array.
See Algorithms for Competitive Programming site for a great explanation: Search the subarray with the maximum/minimum sum
Below is an implementation of the algorithm:
1
2
3
4
5
6
7
8
9
int kadane(const vector<int>& nums) {
int max_sum = 0, local_max = 0;
for (auto i: nums) {
local_max = max(i, local_max + i);
max_sum = max(max_sum, local_max);
}
return max_sum;
}
Implementation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
int kadane(const vector<int>& nums, int reverse=1) {
int sum = 0, temp = 0;
for (auto i: nums) {
temp = max(i * reverse, temp + i * reverse);
sum = max(sum, temp);
}
return sum;
}
int maxAbsoluteSum(vector<int>& nums) {
return max(kadane(nums), kadane(nums, -1));
}
};