What is the brute force approach and complexity for Maximum Absolute Sum of Any Subarray?

From each start, grow the run one number at a time and keep the largest |sum| with time complexity O(N^2) and space complexity O(1).

What is the optimal approach and complexity for Maximum Absolute Sum of Any Subarray?

Run max-Kadane and min-Kadane together; answer = max(curMax, −curMin) with optimal time complexity O(N) and space complexity O(1).

How do you identify the pattern for Maximum Absolute Sum of Any Subarray?

Look for key signals in the prompt: "absolute sum" indicates Two targets: the largest sum and the most negative sum. Track both.; "contiguous subarray" indicates Both targets are Kadane runs, one with max and one with min.; "largest absolute value" indicates The answer is max(largest sum, −smallest sum): one pass, two runs..

Maximum Absolute Sum of Any Subarray

Medium·LeetCode #1749 Pro OnlySlight Variation

LeetCode

Problem Statement

You are given an integer array nums. The absolute sum of a subarray is the size of its sum, with the sign removed. If a subarray adds up to -8, its absolute sum is 8.

Find the largest absolute sum of any subarray and return it. A subarray is a run of neighbouring numbers. An empty run is allowed and has sum 0, so the answer is never negative.

Input

An integer array nums of length n.

Output

One number: the largest absolute value of the sum of any subarray.

Example 1

Input: nums = [1, -3, 2, 3, -4]

Output: 5

The run [2, 3] sums to 5. The whole array sums to -1, which is only 1 in size, so the run [2, 3] wins.

Example 2

Input: nums = [2, -5, 1, -4, 3, -2]

Output: 8

The run [-5, 1, -4] sums to -8. Its absolute value, 8, is the largest.

Constraints

• 1 ≤ nums.length ≤ 10^5
• −10^4 ≤ nums[i] ≤ 10^4

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“absolute sum”

→ Two targets: the largest sum and the most negative sum. Track both.

“contiguous subarray”

→ Both targets are Kadane runs, one with max and one with min.

“largest absolute value”

→ The answer is max(largest sum, −smallest sum): one pass, two runs.

Approach Complexity Ladder

Brute Force — every subarray, running sumO(N^2)O(1)

From each start, grow the run one number at a time and keep the largest |sum|

Optimal — one pass, track the biggest and the smallest runO(N)O(1)

Run max-Kadane and min-Kadane together; answer = max(curMax, −curMin)

Brute Force Intuition

Try every start. From each start, add one number at a time, take the absolute value of that running sum, and keep the largest one seen.

Recognition rule for this sub-pattern:

cur = max(x, cur + x); best = max(best, cur).

Remember this · DP — Kadane / Subarray

Trigger

Maximum (or minimum) sum/product of a contiguous subarray, stock buy/sell, circular arrays.

Think

Is the best subarray ending at i either "i alone" or "best ending at i−1, plus i"?

Key question

Should I extend or restart?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like DP — Kadane / Subarray translate into production architectures and low-level memory mechanics.

LLD Architecture