Implement a function to find the maximum sum subarray (Kadane's algorithm).

Kadane's algorithm efficiently finds the maximum sum of a contiguous subarray within a one-dimensional array of numbers. It achieves this with optimal O(n) time complexity and O(1) space complexity.

Mechanics and Why it Works

This algorithm is a classic example of dynamic programming. It iterates through the array, maintaining two key variables: current_max and global_max.
current_max tracks the maximum sum of a subarray ending at the current position. At each element x, current_max is updated to be the maximum of x (starting a new subarray from x) or current_max + x (extending the previous subarray). This is the core DP transition.
global_max stores the overall maximum sum found across all subarrays encountered so far. After updating current_max, global_max is updated to be the maximum of itself and current_max.

This approach naturally handles arrays containing all negative numbers; global_max will correctly return the largest (least negative) single element, as current_max would reset to the current negative number if extending the sum made it smaller.

def max_subarray_sum(nums):
    if not nums:
        # Handle empty array: return 0 or raise ValueError
        return 0 
    
    current_max = nums[0]
    global_max = nums[0]
    
    for x in nums[1:]:
        current_max = max(x, current_max + x)
        global_max = max(global_max, current_max)
        
    return global_max

In the Interview, Also Mention…

Beyond handling empty arrays (returning 0 or raising an error), discuss edge cases like single-element arrays (the algorithm correctly returns that element). Emphasize that Kadane's is a foundational algorithm. It can be extended to solve more complex problems, such as finding the maximum sum submatrix in a 2D array or the maximum sum circular subarray, by applying variations of this core logic. This demonstrates a deeper understanding of algorithmic patterns and their broader applicability.