1749. Maximum Absolute Sum of Any Subarray
Maximum Absolute Sum of Any Subarray (LeetCode 1749) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Dynamic Programming (DP) Patterns pattern, in the 1D Array (Kadane's Algorithm for Max/Min Subarray) subpattern.
How to solve Maximum Absolute Sum of Any Subarray
Maximum Absolute Sum of Any Subarray is a Kadane's Algorithm problem, part of Dynamic Programming (DP) Patterns. Master Kadane's algorithm for finding maximum (or minimum) subarray sum in O(n) time.
Work towards the solution in these steps:
- Consider how dynamic programming can help efficiently compute sums over subarrays without redundant calculations.
- Recall Kadane's algorithm which finds the maximum subarray sum in linear time by tracking current and global maxima.
- 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.
The reference solution runs in O(n) time and O(1) space.
The Maximum Absolute Sum of Any Subarray solution and editorial walks through the full approach with reference code.
Problem statement
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).
Return the maximum absolute sum of any (possibly empty) subarray of nums.
Note that abs(x) is defined as follows: If x is a negative integer, then abs(x) = -x.
If x is a non-negative integer, then abs(x) = x.
Example 1: Input: nums = [1,-3,2,3,-4] Output: 5 Explanation: The subarray [2,3] has absolute sum = abs(2+3) = abs(5) = 5.
Example 2: Input: nums = [2,-5,1,-4,3,-2] Output: 8 Explanation: The subarray [-5,1,-4] has absolute sum = abs(-5+1-4) = abs(-8) = 8.
Constraints: 1 <= nums.length <= 105 -104 <= nums[i] <= 104
Topics and companies
Topics: nan.
Reported in interviews at nan.
How to practise Maximum Absolute Sum of Any Subarray on Thita.ai
Starter code is provided in C, C#, C++, dart, elixir, erlang, Go, Java, JavaScript, Kotlin, PHP, Python, python3, racket, Ruby, Rust, Scala, Swift and TypeScript. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(1) space.
Open Maximum Absolute Sum of Any Subarray in the code editor, or read the Maximum Absolute Sum of Any Subarray editorial for a worked solution with its approach and complexity analysis.
Where Maximum Absolute Sum of Any Subarray sits in the DSA pattern sheet
- Dynamic Programming (DP) Patterns pattern guide
- 1D Array (Kadane's Algorithm for Max/Min Subarray) subpattern
- The full DSA patterns sheet
Problems related to Maximum Absolute Sum of Any Subarray
Other problems that use the same 1D Array (Kadane's Algorithm for Max/Min Subarray) and Dynamic Programming (DP) Patterns techniques:
- Maximum Product Subarray — Medium, same subpattern
- Maximum Subarray — Medium, same subpattern
- Maximum Sum Circular Subarray — Medium, same subpattern
- Best Time to Buy and Sell Stock — Easy, same pattern
- Best Time to Buy and Sell Stock II — Medium, same pattern
- Best Time to Buy and Sell Stock III — Hard, same pattern
Maximum Absolute Sum of Any Subarray FAQ
What is the LeetCode number of Maximum Absolute Sum of Any Subarray?
Maximum Absolute Sum of Any Subarray is LeetCode problem 1749, rated Medium.
What pattern is used to solve Maximum Absolute Sum of Any Subarray?
Maximum Absolute Sum of Any Subarray is a Kadane's Algorithm problem. It belongs to the Dynamic Programming (DP) Patterns pattern, in the 1D Array (Kadane's Algorithm for Max/Min Subarray) subpattern.
What is the time complexity of Maximum Absolute Sum of Any Subarray?
The reference solution runs in O(n) time and O(1) space.
Which companies ask Maximum Absolute Sum of Any Subarray?
Maximum Absolute Sum of Any Subarray has been reported in interviews at nan.