Maximum Subarray — LeetCode #53 (Medium)
Tags: Array, Divide and Conquer, Dynamic Programming
Related patterns: Dynamic Programming, Sliding Window
Brute Force approach
Time complexity: O(n²). Space complexity: O(1).
The brute-force approach checks all possible subarrays to find the one with the maximum sum. This is simple to understand but inefficient for larger arrays.
The time complexity is O(n²) because we have two nested loops iterating through the array. The space complexity is O(1) since we are only using a few variables to store sums.
- Step 1: Initialize a variable to store the maximum sum found, starting with a very small number.
- Step 2: Use two nested loops to generate all possible subarrays.
- Step 3: For each subarray, calculate its sum and update the maximum sum if the current sum is greater.
For nums = [-2,1,-3,4,-1,2,1,-5,4]:
1. i=0, j=0: sum = -2, max_sum = -2
2. i=0, j=1: sum = -1, max_sum = -1
3. i=0, j=2: sum = -4, max_sum = -1
4. i=0, j=3: sum = 0, max_sum = 0
5. i=0, j=4: sum = -1, max_sum = 0
6. i=0, j=5: sum = 1, max_sum = 1
... (continue until the end)
Optimal Solution approach
Time complexity: O(n). Space complexity: O(1).
The optimal solution uses Kadane's algorithm, which efficiently finds the maximum subarray sum in a single pass through the array. It keeps track of the current subarray sum and updates the maximum sum found so far.
The time complexity is O(n) because we only make a single pass through the array. The space complexity is O(1) since we are using a constant amount of space.
- Step 1: Initialize two variables: max_sum to the first element and current_sum to the first element.
- Step 2: Iterate through the array starting from the second element.
- Step 3: For each element, update current_sum to be the maximum of the current element or current_sum plus the current element.
- Step 4: Update max_sum if current_sum is greater than max_sum.
For nums = [-2,1,-3,4,-1,2,1,-5,4]:
1. Start: max_sum = -2, current_sum = -2
2. num = 1: current_sum = max(1, -2 + 1) = 1, max_sum = max(-2, 1) = 1
3. num = -3: current_sum = max(-3, 1 - 3) = -2, max_sum = 1
4. num = 4: current_sum = max(4, -2 + 4) = 4, max_sum = max(1, 4) = 4
5. num = -1: current_sum = max(-1, 4 - 1) = 3, max_sum = 4
6. num = 2: current_sum = max(2, 3 + 2) = 5, max_sum = max(4, 5) = 5
7. num = 1: current_sum = max(1, 5 + 1) = 6, max_sum = max(5, 6) = 6
8. num = -5: current_sum = max(-5, 6 - 5) = 1, max_sum = 6
9. num = 4: current_sum = max(4, 1 + 4) = 5, max_sum = 6
Key Insights
- Kadane's algorithm is a powerful technique for solving maximum subarray problems efficiently.
- Understanding how to maintain a running sum can greatly simplify many problems involving arrays.
Common Mistakes
- Not initializing the maximum sum correctly, which can lead to incorrect results.
- Forgetting to handle negative numbers properly, which can affect the current sum calculation.
Interview Tips
- Always explain your thought process while coding; it helps the interviewer understand your approach.
- Consider edge cases, such as arrays with all negative numbers or a single element.
- Practice writing both brute-force and optimal solutions to strengthen your understanding of the problem.
