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

Mar 28, 2025 - 04:49

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