# Maximum Subarray ## # Solution

The brute force solution would:

• enumerate subarrays in a nested for loop ()
• calculate sum ()
• update if current subarray has largest sum ()

So in total takes time.

### # 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
• current local maximum sum (at this given point)
• global maximum sum seen so far

Complexity:

• time:
• space:
def maxSubArray(self, nums: List[int]) -> int:
n = len(nums)
curr_sum = max_sum = nums

for num in nums[1:]:
curr_sum = max(num, curr_sum+num)
max_sum = max(curr_sum,max_sum)
return max_sum


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.

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

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


### # Divide & Conquer (REDO)

Complexity:

• time:
• space:
Last Updated: 5/13/2020, 7:39:18 AM