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

1. 分治算法：

function maxSubarray(A, low, high)
    if high == low
        return (low, high, A[low])
    else
        mid = floor((low + high) / 2)
        (leftLow, leftHigh, leftSum) = maxSubarray(A, low, mid)
        (rightLow, rightHigh, rightSum) = maxSubarray(A, mid + 1, high)
        (crossLow, crossHigh, crossSum) = maxCrossingSubarray(A, low, mid, high)
        if leftSum >= rightSum and leftSum >= crossSum
            return (leftLow, leftHigh, leftSum)
        else if rightSum >= leftSum and rightSum >= crossSum
            return (rightLow, rightHigh, rightSum)
        else
            return (crossLow, crossHigh, crossSum)

function maxCrossingSubarray(A, low, mid, high)
    leftSum = A[mid]
    sum = 0
    for i = mid downto low
        sum += A[i]
        if sum > leftSum
            leftSum = sum
            maxLeft = i
    rightSum = A[mid + 1]
    sum = 0
    for j = mid + 1 to high
        sum += A[j]
        if sum > rightSum
            rightSum = sum
            maxRight = j
    return (maxLeft, maxRight, leftSum + rightSum)

时间复杂度：O(nlogn)

2. 分治算法 + 动态规划：

function maxSubarray(A, low, high)
    if high == low
        return (low, high, A[low])
    else
        mid = floor((low + high) / 2)
        (leftLow, leftHigh, leftSum) = maxSubarray(A, low, mid)
        (rightLow, rightHigh, rightSum) = maxSubarray(A, mid + 1, high)
        (crossLow, crossHigh, crossSum) = maxCrossingSubarray(A, low, mid, high)
        if leftSum >= rightSum and leftSum >= crossSum
            return (leftLow, leftHigh, leftSum)
        else if rightSum >= leftSum and rightSum >= crossSum
            return (rightLow, rightHigh, rightSum)
        else
            return (crossLow, crossHigh, crossSum)

function maxCrossingSubarray(A, low, mid, high)
    leftSum = A[mid]
    sum = 0
    for i = mid downto low
        sum += A[i]
        if sum > leftSum
            leftSum = sum
            maxLeft = i
    rightSum = A[mid + 1]
    sum = 0
    for j = mid + 1 to high
        sum += A[j]
        if sum > rightSum
            rightSum = sum
            maxRight = j
    return (maxLeft, maxRight, leftSum + rightSum)

function maxSubarrayLinear(A)
    maxSoFar = maxEndingHere = A[1]
    low = maxLow = high = 1
    for i = 2 to length(A)
        if maxEndingHere > 0
            maxEndingHere += A[i]
        else
            maxEndingHere = A[i]
            low = i
        if maxEndingHere > maxSoFar
            maxSoFar = maxEndingHere
            maxLow = low
            high = i
    return (maxLow, high, maxSoFar)

function maxSubarrayHybrid(A, low, high)
    if high - low + 1 <= 128
        return maxSubarrayLinear(A[low...high])
    else
        mid = floor((low + high) / 2)
        (leftLow, leftHigh, leftSum) = maxSubarrayHybrid(A, low, mid)
        (rightLow, rightHigh, rightSum) = maxSubarrayHybrid(A, mid + 1, high)
        (crossLow, crossHigh, crossSum) = maxCrossingSubarray(A, low, mid, high)
        if leftSum >= rightSum and leftSum >= crossSum
            return (leftLow, leftHigh, leftSum)
        else if rightSum >= leftSum and rightSum >= crossSum
            return (rightLow, rightHigh, rightSum)
        else
            return (crossLow, crossHigh, crossSum)

时间复杂度：O(nlogn)