1749. Maximum Absolute Sum of Any Subarray

How to solve Maximum Absolute Sum of Any Subarray (LeetCode 1749): the approach in brief

The problem

You are given an integer array nums. The absolute sum of a subarray [numsl, numsl+1, ..., numsr-1, numsr] is abs(numsl + numsl+1 + ... + numsr-1 + numsr).

Pattern

Maximum Absolute Sum of Any Subarray is a Dynamic Programming (DP) Patterns problem, in the 1D Array (Kadane's Algorithm for Max/Min Subarray) subpattern. The pattern covers fibonacci, Kadane, knapsack, LCS, LIS, edit distance, grid paths, and word break

Master Kadane's algorithm for finding maximum (or minimum) subarray sum in O(n) time.

Approach outline

1. Consider how dynamic programming can help efficiently compute sums over subarrays without redundant calculations.
2. Recall Kadane's algorithm which finds the maximum subarray sum in linear time by tracking current and global maxima.
3. Think about how to adapt Kadane's algorithm to also handle subarrays with the minimum sum, since absolute values depend on both positive and negative sums.

Complexity

The reference solution runs in O(n) time and O(1) space.

Asked at

Maximum Absolute Sum of Any Subarray has been reported in interviews at nan.