分治法求最大子段的伪代码

分治法（Divide and Conquer）通常用于解决那些可以通过分解成较小的相同或相似问题并递归地解决它们的问题。对于找最大子段和（Maximum Subarray Sum），一种常见的使用分治法的方法是Kadane's Algorithm，也称为动态规划的一个变种。

以下是一个简单的伪代码描述：

function maxSubArraySum(arr, low, high):
    if low == high:  // 基准条件，只有一个元素
        return arr[low]
    
    // 找到左半部分的最大子数组和 mid 是分割点
    mid = (low + high) / 2
    leftMax = maxSubArraySum(arr, low, mid)
    rightMax = maxSubArraySum(arr, mid+1, high)

    // 分割后最大子数组可能是跨越左右两部分的
    crossMax = arr[mid]  # 当前中间值
    tempSum = arr[mid]     # 初始化为中间值，可能成为左侧的最大和
    for i from mid - 1 to low - 1:
        tempSum += arr[i]
        if tempSum > crossMax:
            crossMax = tempSum

    # 比较哪一边包含更大和的部分
    return max(leftMax, rightMax, crossMax)