[LeetCode] 53. Maximum Subarray

Problem : https://leetcode.com/problems/maximum-subarray/

O( N ) time complexity solution is based on DP.

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
    
        result = -2 ** 31
        tmp = 0
        
        for i in range(len(nums)):
            # restart sub-array from i if its sum less than nums[i]
            tmp = max(tmp + nums[i], nums[i])            
            result = max(result, tmp)

        return result

Divide and conquer solution:

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        
        def helper(start, end):
            if end - start == 1:
                return nums[start]
            
            mid = start + (end - start) // 2
            
            # max of left sub-array
            left_max = helper(start, mid)
            
            # max of right sub-array
            right_max = helper(mid, end)
        
            # max of middle
            mid_max = nums[mid]
            t = mid_max
            
            for i in range(mid-1, start-1, -1):
                t += nums[i]
                mid_max = max(mid_max, t)
                
            t = mid_max
            for i in range(mid+1, end): 
                t += nums[i]
                mid_max = max(mid_max, t)
            
            return max(left_max, mid_max, right_max)
            
         
        return helper(0, len(nums))