Maximum Subarray Sum
Given an array of integers nums, write a function maxSubarraySum to find the maximum sum of a contiguous subarray within the array and return that maximum sum. The subarray must be contiguous, meaning that the elements must appear consecutively in the original array.
Examples
Input: nums = [2, 3, -2, 4] Output: 7 Explanation: Maximum sum is 2 + 3 + (-2) + 4 = 7. Input: nums = [1, -1, -5, -4] Output: 1 Explanation: The maximum sum is 1, which is the single element with the highest value.
Can you come up with a solution with a O(n) time complexity?
Can you come up with a solution with a O(1) space complexity?
Our solution for finding the maximum subarray sum processes the input array by iterating through it while maintaining two variables: max_current and max_global. The max_current variable keeps track of the maximum sum of the subarray ending at the current position, while max_global stores the maximum sum encountered so far.
For each element in the array, we update max_current by taking the maximum of the current element alone or the sum of the current element and max_current. This decision ensures that max_current always holds the maximum sum of the subarray that ends at the current element. We then update max_global to be the maximum of max_global and max_current.
If the input array is empty, the function returns 0 since there are no subarrays to consider.
This approach uses a simple iteration and a couple of variables, making it both straightforward and efficient.
from typing import List
def max_subarray_sum(nums: List[int]) -> int:
if not nums:
return 0
# Initialize the variables
max_current = max_global = nums[0]
# Iterate through the array
for num in nums[1:]:
max_current = max(num, max_current + num)
if max_current > max_global:
max_global = max_current
return max_globalTime Complexity: The solution has a time complexity of O(n), where n is the number of elements in the array. This is because we iterate through the array once, performing constant-time operations (comparison and addition) for each element.
Space Complexity: The solution uses O(1) space since it only requires a fixed amount of extra space for the max_current and max_global variables, regardless of the input size. This makes the solution very efficient in terms of space usage.
This algorithm is known as Kadane's Algorithm.
# O(n) time, O(1) space from typing import List def max_subarray_sum(nums: List[int]) -> int: if len(nums) == 0: return 0 max_sum = curr_sum = nums[0] for i in range(1, len(nums)): curr_sum = max(curr_sum + nums[i], nums[i]) max_sum = max(curr_sum, max_sum) return max_sum # debug your code below print(max_subarray_sum([-1, 2, -3, 4]))