下面代码用分治求“最大连续子段和”，其时间复杂度为（ ）。
int solve(vector<int>& a, int l, int r){
if(l == r) return a[l];
int mid = l + (r - l) / 2;
int left = solve(a, l, mid);
int right = solve(a, mid + 1, r);
int sum = 0, lmax = INT_MIN;
for(int i = mid; i >= l; i--){
sum += a[i];
lmax = max(lmax, sum);
}
sum = 0;
int rmax = INT_MIN;
for(int i = mid + 1; i <= r; i++){
sum += a[i];
rmax = max(rmax, sum);
}
return max({left, right, lmax + rmax});
}
- A. O(n²)
- B. O(n log n)
- C. O(log n)
- D. O(n)
正确答案：B