Try out all O(n^2) subarray and return the max sum.
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].
At the beginning, max_subarray = nums
if not nums: return -1 max_sub =  * len(nums) max_sub = nums 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)
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.
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  right would be  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.