Problem statement

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

Solution 1

We can easily do it with DP in O(n) time. Define by dp[i] maximum sum ending with element with index i. Then we have two options: either continue subarray or take single element.

Complexity

Time and space is O(n).

Code

class Solution:
    def maxSubArray(self, nums):
        dp = [0]*len(nums)
        dp[0] = nums[0]
        for i in range(1, len(nums)):
            dp[i] = max(nums[i], nums[i] + dp[i-1])
        return max(dp)

Solution 2

Also there is divide and conquer solution where we split array into two parts.

Complexity

It is O(n log n) for time and O(n) for space.

Code

class Solution:
    def maxSubArray(self, nums):
        def helper(beg, end):
            if beg + 1 == end: return nums[beg]
            mid = (beg + end)//2
            sum_1 = helper(beg, mid)
            sum_2 = helper(mid, end)
            right = max(accumulate(nums[beg:mid][::-1]))
            left  = max(accumulate(nums[mid:end]))
            return max(sum_1, sum_2, left + right)

        return helper(0, len(nums))