53. Maximum Subarray

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Example 2:

Input: nums = [1]
Output: 1

Example 3:

Input: nums = [0]
Output: 0

Example 4:

Input: nums = [-1]
Output: -1

Example 5:

Input: nums = [-2147483647]
Output: -2147483647

Constraints:
-1 <= num.length <= 2*10^4

-2^{31} <= num[i] <= 2^{31}-1

Solution in python:
1.Kadane algorithm

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        sum_value = 0
        max_subseq = nums[0]
        for i in range(len(nums)):
            sum_value += nums[i]
            if sum_value > max_subseq:
                max_subseq = sum_value
            if sum_value < 0:
                sum_value = 0;
        return max_subseq

Complexity analysis:

• Time complexity:O(n).
• Space complexity:O(1).

2.Divide and conquer

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        def max_subseq(left, right, num):
            if left == right:
                return num[left]
            middle = (left+right)//2
            max_left = max_subseq(left, middle, num)
            max_right = max_subseq(middle+1, right, num)
            sum_left = sum_right = 0
            i, j= middle, middle + 1
            max_middle_left = num[i]
            max_middle_right = num[j]
            while i >= left:
                sum_left += num[i]
                if sum_left >= max_middle_left:
                    max_middle_left = sum_left
                i -= 1
            while j <= right:
                sum_right += num[j]
                if sum_right >= max_middle_right:
                    max_middle_right = sum_right
                j += 1
            max_middle = max_middle_left + max_middle_right
            return max(max_left, max_middle, max_right)
        return max_subseq(0, len(nums)-1, nums)

Complexity analysis:

• Time complexity:O(n\log_{}n).
• Space complexity:O(\log_{}n).