利用分治算法求最大子段和问题。C++

利用分治算法解决最大子段和问题通常采用的是Kadane's算法（也称为动态规划），虽然这不是传统意义上的分治法，但其思想类似。这个算法主要是将问题分解为两个独立的部分，然后分别求解，并合并结果。

以下是C++的基本步骤：

1. **分割**（Divide）：给定一个数组`arr[]`，将其分为两部分，左边部分和右边部分。

2. **递归**（Recursion）：对于每半部分，分别计算它们的最大子段和。如果数组只有一个元素，那么它的子段和就是该元素本身；如果有两个或更多元素，则寻找连续子数组的最大和。

3. **组合**（Combine）：合并这两个子数组的最大子段和。通过比较左半部分的最大子段和、右半部分的最大子段和以及跨越边界时左半部分的最后一个元素加上右半部分的第一个元素的和，选择其中的最大值作为整个数组的最大子段和。

4. **返回结果**：递归到最小子数组（即包含一个元素或空数组）时，停止递归并返回最终的结果。

int maxSubArray(int arr[], int size) {
    if (size <= 1)
        return arr[0];
  
    // 分割数组
    int mid = size / 2;
    int maxLeft = maxSubArray(arr, mid);
    int maxRight = maxSubArray(arr + mid, size - mid);
  
    // 选择和最大子数组
    int maxCrossingSum = INT_MIN; // 初始化为负无穷
    for (int i = mid - 1; i >= 0; i--) { 
        maxCrossingSum = max(maxCrossingSum, arr[i] + maxRight); 
    }
  
    return max(maxLeft, maxRight, maxCrossingSum);
}