伪代码求最大连续子数时间复杂度nlogn

以下是求最大连续子数的伪代码，时间复杂度为nlogn：

function maxSubArray(arr, low, high):
    if low == high:
        return (low, high, arr[low])
        
    mid = (low + high) // 2
    
    leftLow, leftHigh, leftSum = maxSubArray(arr, low, mid)
    rightLow, rightHigh, rightSum = maxSubArray(arr, mid+1, high)
    crossLow, crossHigh, crossSum = maxCrossingSubArray(arr, low, mid, high)
    
    if leftSum >= rightSum and leftSum >= crossSum:
        return (leftLow, leftHigh, leftSum)
    elif rightSum >= leftSum and rightSum >= crossSum:
        return (rightLow, rightHigh, rightSum)
    else:
        return (crossLow, crossHigh, crossSum)

function maxCrossingSubArray(arr, low, mid, high):
    leftSum = float('-inf')
    sum = 0
    for i in range(mid, low-1, -1):
        sum += arr[i]
        if sum > leftSum:
            leftSum = sum
            maxLeft = i
            
    rightSum = float('-inf')
    sum = 0
    for i in range(mid+1, high+1):
        sum += arr[i]
        if sum > rightSum:
            rightSum = sum
            maxRight = i
            
    return (maxLeft, maxRight, leftSum+rightSum)

该算法的时间复杂度为nlogn，因为它使用了分治策略，将问题分解为更小的子问题并递归求解。在每个递归层次中，算法将数组分成两个子数组，并在O(n)的时间内找到跨越中点的最大子数组。因此，该算法的时间复杂度为nlogn。