单选题 适中
#24869

下面代码用分治求“最大连续子段和”,其时间复杂度为()。 import sys def solve(a , l , r): if l == r: return…

下面代码用分治求“最大连续子段和”,其时间复杂度为()。

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))
未登录也能判分,登录后才会记录
答案与解析
正确答案:B
这道题暂未补解析。