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
- The maximum absolute sum is the larger of the maximum subarray sum and the absolute value of the minimum subarray sum.
- Run Kadane's algorithm twice in the same pass: one for the maximum, one for the minimum.
- Both are standard DP recurrences:
max_end = max(max_end + x, x)andmin_end = min(min_end + x, x). - 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 = 0and forgetting the empty-subarray allowance: here 0 is a valid answer, so this initialisation is correct. - Using
absonmax_endonly 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.