BinarySearch 0986 Maximum Absolute Value of Sublist

Problem statement

https://binarysearch.com/problems/Maximum-Absolute-Value-of-Sublist/

Solution

Equal to 1749. Maximum Absolute Sum of Any Subarray.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, A):
        def kadane(nums):
            dp = [0]*len(nums)
            dp[0] = nums[0]
            for i in range(1, len(nums)):
                dp[i] = max(nums[i], nums[i] + dp[i-1])
            return max(dp)
        
        if not A: return 0
        return max(kadane(A), kadane([-x for x in A]))