Max Subarray Sum Problem: Efficient Solution with Kadane’s Algorithm

The Max Subarray Sum Problem asks you to identify the maximum sum of any contiguous subarray within an array of integers. For example, given the array [−2,1,−3,4,−1,2,1,−5,4], the maximum sum is 6.

To solve this problem efficiently, we can use Kadane's Algorithm. The algorithm works by maintaining two variables: one to track the current subarray sum (which starts at each element and tries to extend as far as possible), and another to keep track of the maximum sum found so far.

The key idea is that if adding a new element to the current subarray does not increase the sum, we start a new subarray from the current element. This is because any subarray that ends at an earlier point plus the current element will always be smaller than starting anew from the current element.

The algorithm iterates through the array once, updating these two variables as it goes. At each step, it checks if the current element should start a new subarray and updates the maximum sum accordingly.

def max_subarray_sum(nums):
    # Initialize variables to keep track of the maximum sum and current sum
    max_sum = float('-inf')
    current_sum = 0

    for num in nums:
        # Update the current subarray sum by including the current element
        current_sum += num

        # Update the maximum sum if the current subarray sum is greater
        if current_sum > max_sum:
            max_sum = current_sum

        # Reset the current sum to zero if it becomes negative (step 2)
        if current_sum < 0:
            current_sum = 0

    return max_sum

This implementation runs in O(n) time complexity, where n is the length of the array, and uses O(1) space. It efficiently finds the maximum subarray sum by maintaining a running total and resetting it when necessary.

Time Complexity: The algorithm runs in O(n) time, where n is the length of the input array. This is because we traverse each element exactly once.

Space Complexity: The space complexity is O(1) since we only use a constant amount of extra space to store variables like `max_sum` and `current_sum`, regardless of the size of the input array.