GESP 五级 · GESP 202509 C++ 五级 第 14 题

给定一个整数数组 nums，下面代码找到一个具有最大和的连续子数组，并返回该最大和。则下面说法错误的是（ ）。

int crossSum(vector<int>& nums, int left, int mid, int right) {
    int leftSum = INT_MIN, rightSum = INT_MIN;
    int sum = 0;
    for (int i = mid; i >= left; i--) {
        sum += nums[i];
        leftSum = max(leftSum, sum);
    }
    sum = 0;
    for (int i = mid + 1; i <= right; i++) {
        sum += nums[i];
        rightSum = max(rightSum, sum);
    }
    return leftSum + rightSum;
}

int helper(vector<int>& nums, int left, int right) {
    if (left == right)
        return nums[left];
    int mid = left + (right - left) / 2;
    int leftMax = helper(nums, left, mid);
    int rightMax = helper(nums, mid + 1, right);
    int crossMax = crossSum(nums, left, mid, right);
    return max({leftMax, rightMax, crossMax});
}

int maxSubArray(vector<int>& nums) {
    return helper(nums, 0, nums.size() - 1);
}

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

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

【考点】分治策略｜递归优化｜时间复杂度分析

1. 🎯 考纲定位

GESP 五级"算法与程序设计"模块，重点考核递归与分治思想的综合应用。命题人卡住的是：学生看到递归就只记"这是分治"，却忽略分治必须同时包含「分解」与「合并」两个动作——本题的 merge 体现在 crossSum 计算跨中子数组和，而非简单返回左右最大值。