Given an array of integers, find the contiguous subarray (containing at least one number) that has the largest sum and return its sum.

Function Signature:

from typing import List

def max_subarray_sum(nums: List[int]) -> int:
    """
    Find the maximum sum of a contiguous subarray in the given array.

    Parameters:
    - nums: List of integers.

    Returns:
    - int: Maximum sum of a contiguous subarray.
    """
    # Your code here

Example:

# Input: nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
# Output: 6
# Explanation: The contiguous subarray [4, -1, 2, 1] has the largest sum = 6.

# Input: nums = [1]
# Output: 1

# Input: nums = [5, 4, -1, 7, 8]
# Output: 23

Note:

  • If possible, solve it in O(n) time complexity.

Instructions:

  • Write the max_subarray_sum function to solve the problem.
  • Implement your solution in Python.
  • Provide clear comments in your code.
  • Discuss the time and space complexity of your solution.

As always, we’ll share our solution to this problem tomorrow. Stay tuned 😊