Finds the contiguous subarray within a one-dimensional array of numbers that has the largest sum.

# Maximum Subarray Sum - Kadane's Algorithm
# Description: Finds the contiguous subarray within a one-dimensional array of numbers that has the largest sum.

def max_subarray(nums):
    """
    Find the maximum sum of a contiguous subarray using Kadane's Algorithm.

    This algorithm efficiently solves the maximum subarray problem by 
    dynamically tracking the maximum sum ending at each position.

    Time Complexity: O(n)
    Space Complexity: O(1)

    Args:
        nums (list of int): Input array of integers

    Returns:
        int: Maximum sum of any contiguous subarray

    Raises:
        ValueError: If the input list is empty

    Example:
        >>> max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4])
        6
        >>> max_subarray([1])
        1
        >>> max_subarray([-1, -2, -3])
        -1
    """
    # Handle empty input
    if not nums:
        raise ValueError("Input list cannot be empty")

    # Initialize with the first element
    max_sum = current_sum = nums[0]

    # Iterate through the array starting from the second element
    for num in nums[1:]:
        # Decide whether to start a new subarray or extend the current one
        # This is the core of Kadane's algorithm
        current_sum = max(num, current_sum + num)

        # Update the overall maximum sum if needed
        max_sum = max(max_sum, current_sum)

    return max_sum

def max_subarray_with_indices(nums):
    """
    Enhanced version of max_subarray that returns the subarray indices 
    along with the maximum sum.

    Args:
        nums (list of int): Input array of integers

    Returns:
        tuple: (max_sum, start_index, end_index)

    Example:
        >>> max_subarray_with_indices([-2, 1, -3, 4, -1, 2, 1, -5, 4])
        (6, 3, 6)
    """
    # Handle empty input
    if not nums:
        raise ValueError("Input list cannot be empty")

    max_sum = current_sum = nums[0]
    max_start = max_end = start = 0

    for end in range(1, len(nums)):
        # Reset start if current_sum becomes negative
        if current_sum + nums[end] < nums[end]:
            start = end
            current_sum = nums[end]
        else:
            current_sum += nums[end]

        # Update max_sum and indices if current_sum is larger
        if current_sum > max_sum:
            max_sum = current_sum
            max_start = start
            max_end = end

    return max_sum, max_start, max_end