Brute force
Try out all O(n^2) subarray and return the max sum.
Dynamic programming
The basic idea is to record all the maximum subarray that ends at all i. and return the max.
How to construct a maximum subarray
If we have had a maximum subarray that ends on i – 1, to determine the maximum subarray that ends on i, we can either
- add maximum subarray that ends on i – 1 with nums[i]
- start a new maximum subarray with only nums[i]
We will choose 1 if max_subarray[i – 1] + nums[i] > nums[i].
Base case:
At the beginning, max_subarray[0] = nums[0]
if not nums:
return -1
max_sub = [0] * len(nums)
max_sub[0] = nums[0]
for i in range(1,len(nums)):
max_sub[i] = max(max_sub[i - 1] + nums[i], nums[i])
return max(max_sub)
Divide and conquer
def maxSubArray(self, nums: 'List[int]') -> 'int':
"""
"""
def find_mid(nums, l, r, m):
"""
Find the maxsubarray that ends on m,
and the maxsubarray that starts on m + 1, concat th eresult
"""
cur_sum = 0
left_sum = - float('inf')
for i in range(m, l - 1, -1):
cur_sum += nums[i]
left_sum = max(left_sum, cur_sum)
right_sum = - float('inf')
cur_sum = 0
for i in range(m + 1, r + 1):
cur_sum += nums[i]
right_sum = max(right_sum, cur_sum)
return right_sum + left_sum
def find_recur(nums, l, r):
if (l == r):
return nums[l]
m = (l + r) // 2
return max(find_recur(nums, l, m),
find_recur(nums, m + 1, r),
find_mid(nums, l, r, m))
return find_recur(nums, 0, len(nums) - 1)
Bugs
Didn’t init the left_sum and right_sum to -float(‘inf’).
In case of nums of size 2. The find middle will simply return 0. But the middle didn’t include anything so we should return -inf in that case.
Find middle
At first, I did something more complicated so my code can strictly divide the three cases:
EG in [1,2,3,4] left would be [1] right would be [4] and middle would be [2,3]. But it leads to complicated code because you have to divide cases into even and odd and so on.
a simpler solution
We can just use (l + r) //2 as the middle and find the max subarray that contains the middle.
It might overlap.
[10,20,-1,-1] we have l = 0, m = 1 and r = 3. find_recur(nums, l, m) will find the max subarray in [10, 20]. It is 30. find_mid will find the maxsubarray that contains nums[m]. In this case, find_mid finds 30 as well. But overlap is ok because we only want the max.