Given an integer array nums
, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Example 1:
Input: nums = [-2,1,-3,4,-1,2,1,-5,4] Output: 6 Explanation: [4,-1,2,1] has the largest sum = 6.
Example 2:
Input: nums = [1] Output: 1
Example 3:
Input: nums = [0] Output: 0
Example 4:
Input: nums = [-1] Output: -1
Example 5:
Input: nums = [-2147483647] Output: -2147483647
Constraints:
1 <= nums.length <= 2 * 104
-231 <= nums[i] <= 231 - 1
Source
def max_subarray(nums):
"""Dynamic Programming solution
Time Complexity O(n)
Space complexity O(n)
"""
dp = [0]*len(nums)
max_sum = dp[0] = nums[0]
for i in range(1, len(nums)):
dp[i] = max(dp[i-1]+nums[i], nums[i])
if dp[i] > max_sum:
max_sum = dp[i]
return max_sum
def max_subarray(nums):
"""Kadane's Algorithm.
Time Complexity O(n)
Space complexity O(1)
"""
if not nums:
return None
curr_sum = max_sum = nums[0]
for number in nums[1:]:
curr_sum = max(number, curr_sum + number)
max_sum = max(max_sum, curr_sum)
return max_sum
def max_subarray(nums):
"""Variation of Kadane's Algorithm (bit faster).
Time Complexity O(n)
Space complexity O(1)
"""
max_sum = None
curr_sum = 0
for number in nums:
curr_sum += number
if max_sum is None or max_sum < curr_sum:
max_sum = curr_sum
if curr_sum < 0:
curr_sum = 0
return max_sum
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
max_subarray(nums)
6
nums = [-2147483647]
max_subarray(nums)
-2147483647
nums = [8, -19, 5, -4, 20]
max_subarray(nums)
21
nums = [-2, -1]
max_subarray(nums)
-1
nums = [-1,1,2,1]
max_subarray(nums)
4
nums = [1]
max_subarray(nums)
1
nums = [0]
max_subarray(nums)
0
nums = [-1]
max_subarray(nums)
-1
If you have figured out the O(n)
solution, try coding another solution using the divide and conquer approach, which is more subtle.
def max_subarray(nums):
"""divide and conquer approach.
Time Complexity T(n) = O(nlogn)
Space Complexity logn?
+info: https://www.youtube.com/watch?v=yBCzO0FpsVc
"""
def divide(nums, start, end):
"""divide function"""
if (start == end): # Base Case: Only one element
return nums[start]
middle = (start + end) // 2
return max(divide(nums, start, middle),
divide(nums, middle+1, end),
merge(nums, start, middle, end))
def merge(nums, start, middle, end):
"""merge (conquer) function"""
curr_sum = 0
left_sum = -float("inf")
for i in range(middle, start-1, -1): # expand from the middle toward left
curr_sum = curr_sum + nums[i]
if (curr_sum > left_sum):
left_sum = curr_sum # and keep track of max sum
curr_sum = 0 # reset and proceed to the right
right_sum = -float("inf")
for i in range(middle + 1, end + 1): # expand from the middle toward right
curr_sum = curr_sum + nums[i]
if (curr_sum > right_sum):
right_sum = curr_sum # and keep track of max sum
return max(left_sum + right_sum, left_sum, right_sum)
# returning only left_sum + right_sum will fail for [-2, 1]
return divide(nums, 0, len(nums)-1)
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
max_subarray(nums)
6
nums = [-2147483647]
max_subarray(nums)
-2147483647
nums = [8, -19, 5, -4, 20]
max_subarray(nums)
21
nums = [-2, -1]
max_subarray(nums)
-1
nums = [-1,1,2,1]
max_subarray(nums)
4
nums = [1]
max_subarray(nums)
1
nums = [0]
max_subarray(nums)
0
nums = [-1]
max_subarray(nums)
-1