# Maximum Subarray

ArrayPrefix SumDPD&C

## # Solution

### # Brute Force (TLE)

Complexity

time: $O(n^2)$
space: $O(1)$

def maxSubArray(self, nums: List[int]) -> int:
n = len(nums)
res = nums[0]

for i in range(n):
csum = nums[i]
for j in range(i, n):
if i == j:
csum = nums[i]
else:
csum += nums[j]
res = max(res, csum)

return res

1
2
3
4
5
6
7
8
9
10
11
12
13
14

### # Prefix Max

Pick the locally optimal move at each step, and that will lead to the globally optimal solution.

Iterate over the array and update at each step:

• current element num
• current local maximum sum csum
• either start a new array $\rightarrow$ num
• or continue the old array $\rightarrow$ csum + num)
• global maximum sum res

Complexity

time: $O(n)$
space: $O(1)$

def maxSubArray(self, nums: List[int]) -> int:
n = len(nums)
csum = res = nums[0]

for num in nums[1:]:
csum = max(num, csum + num)
res = max(res, csum)
return res

1
2
3
4
5
6
7
8

DP logic:

• if nums[i-1] > 0, include i-1th element
• if nums[i-1] <= 0, start a new array from ith element

Modify the array to track the current local max sum, then update the global max sum res.

Complexity

time: $O(n)$
space: $O(1)$

def maxSubArray(self, nums: List[int]) -> int:
n = len(nums)
res = nums[0]

for i in range(1, n):
if nums[i-1] > 0:
nums[i] += nums[i-1]
res = max(res, nums[i])
return res

1
2
3
4
5
6
7
8
9