---
tags: data_structure_python
---

# Maximum Subarray <img src="https://img.shields.io/badge/-easy-brightgreen">

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

<ins>**Example:**</ins>

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

**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.

## Solution

### Solution 1: Naive approach

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        # o(n^2)

        n = len(nums)
        maxi = -2**31
        for i in range(n):
            for j in range(i, n):
                tmp = sum(nums[i:j+1])
                if tmp > maxi:
                    maxi = tmp
        return maxi

### Solution 2: Divide and Conquer

class Solution:
    def __maxSubArray(self, nums, l, r):
        # Divide and Conquer.
        # o(nlog(n))
        if l == r:
            return nums[l]
        else:
            mid = l + (r - l)//2
            
            leftMax= -2**31
            accu = 0
            for i in range(mid, l-1, -1):
                accu += nums[i]
                if accu > leftMax:
                    leftMax = accu
            
            rightMax= -2**31
            accu = 0
            for i in range(mid+1, r+1):
                accu += nums[i]
                if accu > rightMax:
                    rightMax = accu
            
            maxLeftRight = max(self.__maxSubArray(nums, l, mid),
                               self.__maxSubArray(nums, mid+1, r))
            
            return max(maxLeftRight, leftMax + rightMax)
           
            
    def maxSubArray(self, nums: List[int]) -> int:
        return self.__maxSubArray(nums, 0, len(nums)-1)

### Solution 3: Kadane's Algorithm

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        # Kadane's Algorithm o(n).
        globalMax = nums[0]
        localMax = globalMax
        
        for i in nums[1:]:
            localMax = max(localMax+i,i)
            globalMax = max(localMax, globalMax)
        
        return globalMax