# 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;
}
};