Maximum Subarray

# Kadane Algorithm - O(n) time, O(1) space
def maxSubArray(nums):
    max_current = max_global = nums[0]
    for i in range(1, len(nums)):
        max_current = max(nums[i], max_current + nums[i])
        max_global = max(max_global, max_current)
    return max_global

# With subarray indices
def maxSubArrayWithIndices(nums):
    max_current = max_global = nums[0]
    start = end = temp_start = 0
    
    for i in range(1, len(nums)):
        if nums[i] > max_current + nums[i]:
            max_current = nums[i]
            temp_start = i
        else:
            max_current += nums[i]
        
        if max_current > max_global:
            max_global = max_current
            start = temp_start
            end = i
    
    return max_global, (start, end)

# Divide and Conquer - O(n log n)
def maxSubArrayDC(nums):
    def findMax(low, high):
        if low == high:
            return nums[low]
        mid = (low + high) // 2
        left_max = findMax(low, mid)
        right_max = findMax(mid + 1, high)
        cross_max = findCrossMax(low, mid, high)
        return max(left_max, right_max, cross_max)
    
    def findCrossMax(low, mid, high):
        left_sum = right_sum = 0
        max_left = nums[mid]
        for i in range(mid, low - 1, -1):
            left_sum += nums[i]
            max_left = max(max_left, left_sum)
        max_right = nums[mid + 1]
        for i in range(mid + 1, high + 1):
            right_sum += nums[i]
            max_right = max(max_right, right_sum)
        return max_left + max_right
    
    return findMax(0, len(nums) - 1)