⚡Flashcard Drill➔
NeetCode #776LC-1749MediumGreedy
← Back to All Problems

#776 · #1749 · Maximum Absolute Sum of Any Subarray(任意子数组和的绝对值的最大值)

📌 Problem Statement & Constraints

Given an integer array nums, return the maximum absolute sum of any subarray (the subarray may be empty, giving 0). Constraints: 1 <= nums.length <= 10^5, -10^4 <= nums[i] <= 10^4.

💡 Core Algorithmic Approaches

  1. The maximum absolute sum is the larger of the maximum subarray sum and the absolute value of the minimum subarray sum.
  2. Run Kadane's algorithm twice in the same pass: one for the maximum, one for the minimum.
  3. Both are standard DP recurrences: max_end = max(max_end + x, x) and min_end = min(min_end + x, x).
  4. Take the maximum absolute value seen across both.

💻 Benchmark Python3 Implementation

class Solution:
    def maxAbsoluteSum(self, nums: List[int]) -> int:
        max_end = min_end = 0
        best = 0
        for x in nums:
            max_end = max(max_end + x, x)
            min_end = min(min_end + x, x)
            best = max(best, abs(max_end), abs(min_end))
        return best

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): a single pass tracking both Kadane variants.
💾 Space Complexity
O(1): three scalars.

⚠️ Interview Pitfalls & Follow-ups

  • Only tracking the maximum subarray sum: a large negative subarray can have a larger absolute value.
  • Initialising best = 0 and forgetting the empty-subarray allowance: here 0 is a valid answer, so this initialisation is correct.
  • Using abs on max_end only after the loop: the maximum absolute value can occur at an intermediate index.
  • Assuming the answer is max(abs(min), abs(max)) over elements: it is over subarrays, not single elements.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Greedy Problems