53. Maximum Subarray

# The problem is reformulated as, what is the max sum we can get for all subarrays containing this element as the end element? # Then from base to general cases is easier to get class Solution: def maxSubArray(self, nums): res = {0: nums[0]} for i in range(0, len(nums)): self.maxHelper(nums, i, res) return max(res.values()) def maxHelper(self, nums, i, res): # what's the max sum we can get for all subarray that ENDS at nums[i]? # a dictionary to store results. If only one element, just that element if i in res.keys(): return res[i] # already computed else: # the current max can either be 1) just the current element or 2) curr + the max subarray that ends at i-1 curr_max = max(nums[i], nums[i] + self.maxHelper(nums, i-1, res)) res[i] = curr_max return curr_max