Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
Input: nums = [5,4,-1,7,8]
Output: 23
1 <= nums.length <= 3 * 10^4
-10^5 <= nums[i] <= 10^5
The naive appraoch is always to produce all of the subarrays and find the one that meets the objective. This approach has a time complexity of O(N^3) and space complexity of O(N^2) where N is the size of array.
def maxSubArray(nums):
"""
:type nums: List[int]
:rtype: int
:Time Complexity: O(N^3)
:Space Complexity: O(N^2)
"""
sums = []
for i in range(len(nums)):
for j in range(i, len(nums)):
sub = nums[i : j + 1]
sums.append(sum(sub))
return max(sums)For the optimal solution, we can use the Kadane's algorithm. This approach has a time complexity of O(N) and space complexity of O(1) where N is the size of array.
def maxSubArray(nums):
"""
:type nums: List[int]
:rtype: int
:Time Complexity: O(N)
:Space Complexity: O(1)
"""
current_max = global_max = nums[0]
for i in range(1, len(nums)):
current_max = max(current_max + nums[i], nums[i])
global_max = max(current_max, global_max)
return global_max