# 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:

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

Approach 1: Scan the array and check the sum for each iteration.

# Code (Python)

Approach 1:

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        if not nums:
            return 0
        total = 0
        min_total = float('inf')
        max_subarray = nums[0]
        for num in nums:
            min_total = min(min_total, total)
            total += num
            max_subarray = max(max_subarray, total - min_total)
        return max_subarray
        
class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0
        prev = nums[0]
        best = prev
        for i in range(1, len(nums)):
            prev = max(nums[i], prev + nums[i])
            best = max(best, prev)
        return best

# Code (C++)

Approach 1:

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int maxSum = nums.size() > 0 ? nums[0] : 0;
        int sum = 0;
        for (int i = 0; i < nums.size(); ++i)
        {
            sum += nums[i];
            if (sum > maxSum) maxSum = sum;
            if (sum < 0) sum = 0;
        }
        return maxSum;
    }
};