# Maximum Subarray Problem
[53. Maximum Subarray](https://leetcode.com/problems/maximum-subarray/submissions/)
## Approach 1: Optimized Brute Force
Brute force, but we don't have to reconstruct the subarray each time.
```python
max_sum = -math.inf
for i in range(len(nums)):
cur_sum = 0
for j in range(i, len(nums)):
cur_sum += nums[j] # update the current subarray sum
max_sum = max(max_sum, cur_sum)
return max_sum
```
## Approach 2: [[dp|DP]], [[kadane|Kadane's Algorithm]]
See the linked note.
## Approach 3: [[divide-and-conquer|Divide and Conquer]]
Not as fast but an interesting alternative.
- Best combined sum
- The best sum from left (must adjacent to mid)
- The best sum from right (must adjacent to mid)
- Left half with recursion
- Right half with recursion
```python
def helper(left, right):
nonlocal nums
if left > right:
return -math.inf
mid = (left + right) // 2
curr = best_left_sum = best_right_sum = 0
for i in range(mid - 1, left - 1, -1):
curr += nums[i]
best_left_sum = max(best_left_sum, curr)
curr = 0
for i in range(mid + 1, right + 1):
curr += nums[i]
best_right_sum = max(best_right_sum, curr)
best_combined_sum = nums[mid] + best_left_sum + best_right_sum
left_half = helper(left, mid - 1)
right_half = helper(mid + 1, right)
return max(best_combined_sum, left_half, right_half)
return helper(0, len(nums) - 1)
```