A21085. 下面代码用分治求“最大连续⼦段和”，其时间复杂度为（ ）。import sys def solve(a, l, r): if l == r: return a[l] mid = l + (r - l) // 2 left = solve(a, l, mid) right = solve(a, mid + 1, r) sum_val = 0 lmax = -sys.maxsize - 1 for …

下面代码用分治求“最大连续⼦段和”，其时间复杂度为（    ）。

import sys

def solve(a, l, r):
    if l == r:
        return a[l]

    mid = l + (r - l) // 2

    left = solve(a, l, mid)
    right = solve(a, mid + 1, r)

    sum_val = 0
    lmax = -sys.maxsize - 1
    for i in range(mid, l - 1, -1):
        sum_val += a[i]
        lmax = max(lmax, sum_val)

    sum_val = 0
    rmax = -sys.maxsize - 1
    for i in range(mid + 1, r + 1):
        sum_val += a[i]
        rmax = max(rmax, sum_val)

    return max(left, right, lmax + rmax)


if __name__ == "__main__":
    a1 = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
    print(solve(a1, 0, len(a1)-1))

    a2 = [-5, -3, -1, -4]
    print(solve(a2, 0, len(a2)-1))

    a3 = [10]
    print(solve(a3, 0, 0))