53. Maximum Subarray - divide and conquer

class Solution: def maxSubArray(self, nums): if len(nums) == 0: return 0 elif len(nums) == 1: return nums[0] elif len(nums) == 2: # this is to prevent later usage of (midpoint + 1) indexing. If not will go out of bound return max(nums[0], nums[1], sum(nums)) else: midpoint = len(nums)//2 # choose the end point # find two maxes excluding midpoints larr = nums[0: midpoint] rarr = nums[midpoint+1:] lmax = self.maxSubArray(larr) rmax = self.maxSubArray(rarr) # now find max including midpoints res = nums[midpoint] # iterate through left subarray lresults = [] for low in range(midpoint-1, -1, -1): lres = sum(nums[low: midpoint]) lresults.append(lres) m_lmax = max(lresults) # iterate through right subarray rresults = [] for high in range(midpoint+1, len(nums), 1): rres = sum(nums[midpoint+1: ]) rresults.append(rres) m_rmax = max(rresults) # get the max of results that include mid points mid_max = max(res, res+m_lmax, res+m_rmax, res+m_lmax+m_rmax) return max(lmax, rmax, mid_max)