GESP 五级 · GESP 202603 C++ 五级 第 11 题

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

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});
}

分析时间复杂度时关注循环层数和每层迭代次数，递归算法则分析递归树。注意最坏/最好/平均情况的区别。

分析复杂度时注意外层循环和内层循环的关联。例如内外两层都到n的循环不一定是O(n²)，要看内层是否每次都在缩小。

【考点】分治法｜递归时间复杂度分析｜主定理

本题考察 GESP 五级《算法设计与分析》模块核心考点：分治策略的时间复杂度推导与递归树分析法。命题人特意选取分治求最大子段和，卡住那些只会背结论、不会分析递归工作量的考生。

标准分治框架：递归左右子问题后，需计算跨越中点的最大子段和。跨越部分需从 mid 向左、向右各遍历一次统计前缀和，耗时 O(n)。总递归式 T(n) = 2T(n/2) + O(n)，由主定理得 T(n) = O(n log n)。

错选 O(n) 者混淆了分治与 Kadane 算法思想；错选 O(n²) 者误判递归深度为 O(n)。最阴险细节是跨越计算的两个循环——若只写一句 max(lmax, sum) 而不遍历，复杂度会降为 O(log n)，但代码中必须显式遍历，否则无法得到正确最大子段和。

若改为只求中心点两侧最大前缀和（不跨越），则跨越部分变为 O(1)，总复杂度降为 O(n log n) 中的 O(n) 项消失，即 O(n)；若用前缀和数组预处理，跨越部分可 O(1) 完成，整体仍 O(n log n)。刷到递归题先问：每层工作量和递归深度乘积决定总复杂度。