A60995. 下面代码用分治求“最大连续子段和”，其时间复杂度为（ ）。1 import sys

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

1 import sys
2
3 def solve(a, l, r):
4  if l == r:
5   return a[l]
6
7  mid = l + (r - l) // 2
8
9  left = solve(a, l, mid)
10  right = solve(a, mid + 1, r)
11
12  sum_val = 0
13  lmax = -sys.maxsize - 1
14  for i in range(mid, l - 1, -1):
15   sum_val += a[i]
16   lmax = max(lmax, sum_val)
17   
18  sum_val = 0
19  rmax = -sys.maxsize - 1
20  for i in range(mid + 1, r + 1):
21   sum_val += a[i]
22   rmax = max(rmax, sum_val)
23
24  return max(left, right, lmax + rmax)
25
26 if __name__ == "__main__":
27  a1 = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
28  print(solve(a1, 0, len(a1)-1))
29
30  a2 = [-5, -3, -1, -4]
31  print(solve(a2, 0, len(a2)-1))
32
33  a3 = [10]
34  print(solve(a3, 0, 0))