53_Maximum_Subarray.md

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.

 

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 = [5,4,-1,7,8]
Output: 23
 

Constraints:

1 <= nums.length <= 3 * 104
-105 <= nums[i] <= 105
 

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.

def maxSubArray(self, nums: List[int]) -> int:
        # Kadane's Algorithm
        max_cur = nums[0]
        max_global = nums[0]
        
        for i in range(1, len(nums)):
            max_cur = max(nums[i], max_cur + nums[i])
            if max_cur > max_global:
                max_global = max_cur
                
        return max_global

Runtime: 80 ms, faster than 15.49% of Python3 online submissions for Maximum Subarray.
Memory Usage: 14.9 MB, less than 60.64% of Python3 online submissions for Maximum Subarray.