Teaching Kids Programming – Maximum Absolute Value of Sublist via Kadane’s Algorithm

Teaching Kids Programming: Videos on Data Structures and Algorithms

You are given a list of integers nums. Return the maximum possible abs(nums[i] + nums[i + 1] + … + nums[j]) for any i <= j.

Constraints
0 ≤ n ≤ 100,000 where n is the length of nums
Example 1
Input
nums = [5, -7, -2, 4]
Output
9
Explanation
We can take the sublist [-7, -2] to get abs(-7 + -2) = 9.

Hints:
Is this problem related to the largest sublist sum problem?
Keep track of the prefix sum in addition to the maximum and minimum prefix sum seen so far. How can these three values help you solve the problem?

This problem is very similar to Teaching Kids Programming – Max Subarray Sum by Kadane’s Algorithm and Teaching Kids Programming – Maximum Subarray by Dynamic Programming and Greedy Algorithm except the absolute value part.

Maximum Absolute Value of Sublist via Naive Bruteforce Algorithm

We can certainly bruteforce the pairs – which cost us O(N^2) loop. Then to compute the sum of a sublist e.g. via sum function, it is going to take another O(N) time, thus overall time complexity is O(N^3).

1
2
3
4
5
6
7
8
9
10
11

class Solution:
    def solve(self, nums):
        if not nums:
            return 0
        n = len(nums)
        ans = -math.inf
        for i in range(n):
            for j in range(i, n):
                s = abs(sum(nums[i:j+1]))
                ans = max(ans, s)
        return ans

class Solution:
    def solve(self, nums):
        if not nums:
            return 0
        n = len(nums)
        ans = -math.inf
        for i in range(n):
            for j in range(i, n):
                s = abs(sum(nums[i:j+1]))
                ans = max(ans, s)
        return ans

Maximum Absolute Value of Sublist via Optimised Bruteforce Algorithm

With slight improvement, we can accumulate the sum – thus save O(N) time to invoke the sum function. The following Algorithms take O(N^2) time for bruteforcing the pairs.

1
2
3
4
5
6
7
8
9
10
11
12

class Solution:
    def solve(self, nums):
        if not nums:
            return 0
        n = len(nums)
        ans = -math.inf
        for i in range(n):
            cur = 0
            for j in range(i, n):
                cur += nums[j]
                ans = max(ans, abs(cur))
        return ans        

class Solution:
    def solve(self, nums):
        if not nums:
            return 0
        n = len(nums)
        ans = -math.inf
        for i in range(n):
            cur = 0
            for j in range(i, n):
                cur += nums[j]
                ans = max(ans, abs(cur))
        return ans        

Maximum Absolute Value of Sublist via Kadane’s Algorithm

Kadane’s algorithm is essentially the iterative Dynamic Programming Algorithm. Let f[i] represent the largest sublist sum that ends at index i – we have to choices: we could include the current number, or abandon the previous sublist and start current number as a new sublist.

In this case, we can apply the Kadane‘s algorithm twice – one for maximum value, another for the minimal value – as the absolute value can be in two cases.

1
2
3
4
5
6
7
8
9
10
11
12

class Solution:
    def solve(self, nums):
        if not nums:
            return 0
        ans = abs(nums[0])
        low = nums[0]
        high = nums[0]
        for i in nums[1:]:
            low = min(low + i, i)
            high = max(high + i, i)
            ans = max(ans, -low, abs(high))
        return ans

class Solution:
    def solve(self, nums):
        if not nums:
            return 0
        ans = abs(nums[0])
        low = nums[0]
        high = nums[0]
        for i in nums[1:]:
            low = min(low + i, i)
            high = max(high + i, i)
            ans = max(ans, -low, abs(high))
        return ans

The time complexity is O(N) as we need only iterating the numbers once. The space complexity is O(1) constant.

–EOF (The Ultimate Computing & Technology Blog) —