1749.maximum-absolute-sum-of-any-subarray.md

1749. Maximum Absolute Sum of Any Subarray

Key Insights

The maximum absolute sum of any subarray could be either:

• The positive maximum subarray sum.
• The negative minimum subarray sum, its absolute value is the candidate of the answer.

So we have to keep track of both the maximum and minimum subarray sum. We can use the similar idea as 53. Maximum Subarray to solve this problem.

1, -3, -2

1   1   1   // local max
1  -3  -5   // local min
1   3   5   // global max

Dynamic Programming

fun maxAbsoluteSum(nums: IntArray): Int {
    val n = nums.size
    val localMax = IntArray(n)
    val localMin = IntArray(n)
    localMax[0] = nums.first()
    localMin[0] = nums.first()
    var globalMax = abs(nums.first())
    for (i in 1 until n) {
        localMax[i] = maxOf(localMax[i - 1] + nums[i], nums[i])
        localMin[i] = minOf(localMin[i - 1] + nums[i], nums[i])
        globalMax = maxOf(globalMax, abs(localMax[i]))
        globalMax = maxOf(globalMax, abs(localMin[i]))
    }
    return globalMax
}

// Or equivalently, we can use two variables to keep track of the local / global max and min.
fun maxAbsoluteSum(nums: IntArray): Int {
    // Local max / min
    var maxEndingHere = 0
    var minEndingHere = 0
    // Global max / min
    var maxSoFar = 0
    var minSoFar = 0
    for (num in nums) {
        maxEndingHere = maxOf(maxEndingHere + num, num)
        minEndingHere = minOf(minEndingHere + num, num)
        maxSoFar = maxOf(maxSoFar, maxEndingHere)
        minSoFar = minOf(minSoFar, minEndingHere)
    }
    return maxOf(maxSoFar, abs(minSoFar))
}

• Time Complexity: O(n)
• Space Complexity: O(1)

Prefix Sum

fun maxAbsoluteSum(nums: IntArray): Int {
    // We need `0` as the base prefix sum.
    var minPrefixSum = 0 // Can't set to Int.MAX_VALUE, `0` is the base.
    var maxPrefixSum = 0 // Can't set to Int.MIN_VALUE, `0` is the base.
    var prefixSum = 0
    var maxSum = Int.MIN_VALUE
    for (num in nums) {
        prefixSum += num
        
        maxSum = maxOf(maxSum, abs(prefixSum - minPrefixSum))
        maxSum = maxOf(maxSum, abs(prefixSum - maxPrefixSum))

        minPrefixSum = minOf(minPrefixSum, prefixSum)
        maxPrefixSum = maxOf(maxPrefixSum, prefixSum)
    }
    return maxSum
}

• Time Complexity: O(n)
• Space Complexity: O(1)