MEDIUM NC#122 Blind #5 Arrays & Hashing / Dynamic Programming (Kadane's Algorithm)
53. Maximum Subarray
š Problem
Given an integer array nums, find the subarray with the largest sum, and return its sum.
š§ Visual Learning Aid
1 Model the input into the right structure
2 Choose the core technique and invariant
3 Execute step-by-step with a sample
4 Validate complexity and edge cases
JS/TS Refreshers
- ā¢Array methods (`push`, `pop`, `shift`, `slice`)
- ā¢Object/Map/Set usage patterns
- ā¢Function parameter and return typing
- ā¢Midpoint overflow-safe math
- ā¢Loop invariants
- ā¢Monotonic condition design
Logical Thinking Concepts
- ā¢Define invariants before coding
- ā¢Check edge cases first (`[]`, single element, duplicates)
- ā¢Estimate time/space before implementation
- ā¢Apply Binary Search reasoning pattern
- ā¢Apply Dynamic Programming reasoning pattern
- ā¢Apply Prefix Sum reasoning pattern
š” Approach
- ā Use Kadane's algorithm to track maximum sum ending at each position
- ā At each index, decide whether to extend the previous subarray or start fresh
- ā Keep track of the global maximum sum seen so far
- ā Time: O(n), Space: O(1)
š ļø Hints & Pitfalls
Hints
- ā¢Use Kadane's algorithm to track maximum sum ending at each position
- ā¢At each index, decide whether to extend the previous subarray or start fresh
- ā¢Keep track of the global maximum sum seen so far
Common Pitfalls
- ā¢Time: O(n), Space: O(1)
š§Ŗ Test Cases
Hidden tests on submit: 3
Test Case 1
Not run Input:
maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4]); Expected:
6 Test Case 2
Not run Input:
maxSubArray([1, 2, 3, 4, 5]); Expected:
15 Test Case 3
Not run Input:
maxSubArray([-1, -2, -3, -4]); Expected:
-1 š Code Editor
š¤ Output