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.

Source: leetcode | Difficulty: EASY
Tags: Dynamic programming

Data structures

Divide and conquer

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

Solutions:
class Solution:

	def maxSubArray(self, nums):
		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):
		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):
		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):
		(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):
		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):
		(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):
		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):
		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):
		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):
		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):
		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):
		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):
		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):

		def dac(X):
			if len(X) == 1:
				return (X[0], X[0], X[0], X[0])
			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]