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.

Difficulty: introductory

Starter code:

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        

Solutions:
class Solution:
     def maxSubArray(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         # i = 0
         # i_keep = 0
         # j = 1
         # j_keep = 1
         # max_sum = nums[0]-1
         # while j < len(nums) and i < j:
         #     temp_sum = sum(nums[i:j])
         #     if temp_sum >= max_sum:
         #         i_keep = i
         #         j_keep = j
         #         max_sum = temp_sum
         #     elif i == j-1:
         #         i += 1
         #         j += 1
         #     j += 1
         # return max_sum
         
         # brute force
         # max_sum = nums[0]
         # for i in range(len(nums)):
         #     for j in range(i,len(nums)+1):
         #         temp_sum = sum(nums[i:j])
         #         if temp_sum > max_sum and i != j:
         #             max_sum = temp_sum
         # return max_sum
 
         # outer loop only
         max_sum = csum = nums[0]
         for num in nums[1:]:
             if num >= csum + num:
                 csum = num
             else:
                 csum += num
             
             if csum > max_sum:
                 max_sum = csum
         
         return max_sum
                 
         


class Solution:
     def maxSubArray(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         if not nums:
             return None
         cur_sum = 0
         max_sum = nums[0]
         for n in nums:
             if cur_sum < 0:
                 cur_sum = n
             else:
                 cur_sum += n
             if cur_sum > max_sum:
                 max_sum = cur_sum
         return max_sum

class Solution:
     def maxSubArray(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         current = 0
         maxsum = -9**99
 
         for i in range(len(nums)):
             if current < 0: current = 0
             current += nums[i]
             maxsum = max(maxsum, current)
         return maxsum

class Solution:
     def maxSubArray(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         current, the_max = [nums[0]]*2
         for num in nums[1:]:
             current = max(num, current + num)
             the_max = max(current, the_max)
         return the_max

class Solution:
     def maxSubArray(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         if len(nums) == 0:
             return 0
         res = curr = nums[0]                           
         for i in range(1, len(nums)):
             curr = max((curr + nums[i], nums[i]))
             res = max((res, curr))
         return res


class Solution:
     def maxSubArray(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         result, curr = nums[0], nums[0]
         i = 1
         while i < len(nums) :
             curr = max(nums[i], curr+nums[i])               
             result = max(curr, result)
             i += 1         
         return result

class Solution:
     def maxSubArray(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         maxSum = maxGlobalSum = nums[0]
 
         for i in range(1, len(nums)):
             if nums[i] > nums[i] + maxSum:
                 maxSum = nums[i]
             else:
                 maxSum += nums[i]
 		
             if maxSum > maxGlobalSum:
                 maxGlobalSum = maxSum
 
         return maxGlobalSum


class Solution:
     def maxSubArray(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         if len(nums) == 0:
             return None
         
         result = nums[0]
         lastMax = nums[0]
     
         for i in range(1, len(nums)):
             lastMax = lastMax + nums[i] if lastMax + nums[i] >= nums[i] else nums[i]
             result = lastMax if lastMax > result else result
         
         return result


class Solution:
     def maxSubArray(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         if len(nums) == 1:
             return nums[0]
         else:
             res = 0
             count = 0
             for i in range(len(nums)):
                 count += nums[i]
                 if count < 0:
                     count = 0
                 else:
                     res = max(res,count)
             if res == 0:
                 return max(nums)
             return res

class Solution:
     def maxSubArray(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         if all(n < 0 for n in nums):
             return max(nums)
         i = 0
         a = 0
         maxsum = 0
         while i < len(nums):
             b = c = 0
             while i < len(nums) and nums[i] <= 0:
                 b += nums[i]
                 i += 1
             while i < len(nums) and nums[i] >= 0:
                 c += nums[i]
                 i += 1
             a = max(a + b + c, c)
             maxsum = max(maxsum, a)
         return maxsum

class Solution:
     def maxSubArray(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         if not nums:
             return 0
         
         curSum = maxSum = nums[0]
         
         for num in nums[1:]:
             curSum = max(num, curSum + num)
             maxSum = max(maxSum, curSum)
 
         return maxSum
 
     


class Solution:
     def maxSubArray(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         # [-2,1,-3,-5]
         curSum = maxSum = nums[0]
         for num in nums[1:]:
             curSum = max(num, curSum + num) # start a new array or use added up array num[1]=1 or num[0]+num[1]=-1
             maxSum = max(maxSum, curSum) # update the max prior = 1 or cursum 1-3-5
 
         return maxSum


class Solution:
     def maxSubArray(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         best = 0
         total = 0
         for n in nums:
             if total+n<0:
                 total=0
             else:
                 total+=n
             print(total)
 
 
             best=max(total,best)
         if max(nums)<0:
             return max(nums)
         return best


class Solution:
     def maxSubArray(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         max_sum = nums[0]
         sum_list = [0] * len(nums)
         sum_list[0] = max_sum
         for i in range(1, len(nums)):
             sum_list[i] = max(nums[i], sum_list[i-1] + nums[i])
             max_sum = max(max_sum, sum_list[i])
         return max_sum
             


class Solution:
     def maxSubArray(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         
         sumlist = [0] * (len(nums) + 1)
         sumlist[0] = 0
         sumMin = 0
         globalMax = nums[0]
         for i in range(1, len(nums) + 1):
             sumlist[i] = sumlist[i - 1] + nums[i - 1]
             print(sumlist[i])
             globalMax = max(sumlist[i] - sumMin, globalMax)
             sumMin = min(sumMin, sumlist[i])
             
         return globalMax

class Solution:
     
     
     def maxSubArray(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         
         def dac (X):
             if len(X) == 1:
                 return X[0], X[0], X[0], X[0] # l, r, m, s
             
             n = len(X)
             nby2 = n // 2
             A = X[:nby2]
             B = X[nby2:]
             l1, r1, m1, s1 = dac(A)
             l2, r2, m2, s2 = dac(B)
             l = max(l1, s1 + l2)
             r = max(r2, s2 + r1)
             m = max(m1, m2, r1 + l2)
             s = s1 + s2
             return l, r, m, s
         
         return dac(nums)[2]