最大子段和问题分治算法伪代码

以下是最大子段和问题的分治算法伪代码：

// 求解最大子段和问题
function maxSubArray(nums) {
    // 递归终止条件
    if (nums.length == 1) {
        return nums[0];
    }
    // 分治过程
    let mid = Math.floor(nums.length / 2);
    let leftMax = maxSubArray(nums.slice(0, mid));
    let rightMax = maxSubArray(nums.slice(mid));
    // 跨越中点的最大子段和
    let crossMax = crossMidMax(nums, mid);
    // 返回三者中的最大值
    return Math.max(leftMax, rightMax, crossMax);
}

// 求解跨越中点的最大子段和
function crossMidMax(nums, mid) {
    let leftMax = -Infinity;
    let leftSum = 0;
    for (let i = mid - 1; i >= 0; i--) {
        leftSum += nums[i];
        leftMax = Math.max(leftMax, leftSum);
    }
    let rightMax = -Infinity;
    let rightSum = 0;
    for (let i = mid; i < nums.length; i++) {
        rightSum += nums[i];
        rightMax = Math.max(rightMax, rightSum);
    }
    return leftMax + rightMax;
}

其中，`maxSubArray`函数用于求解最大子段和问题，`crossMidMax`函数用于求解跨越中点的最大子段和。该算法的时间复杂度为$O(nlogn)$。