单选题 适中
#24788

下面代码用分治求“最大连续子段和”,其时间复杂度为( )。 int solve(vector<int>& a, int l, int r){ if(l == r…

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

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