求最大子数组和（Maximum Subarray Problem）——分治算法实现

---

🎯 问题描述：

给定一个整数数组 nums，找到一个具有最大和的连续子数组（子数组至少包含一个元素），返回该最大和。

例如：

输入：[-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大为 6。

---

🧩 解题思路：分治法（Divide and Conquer）

分治策略核心思想：

将原数组划分为左右两部分，最大子数组和可能出现在以下三个位置之一：

1. 完全在左边子数组
2. 完全在右边子数组
3. 跨越中间（包含左子数组的右端 和 右子数组的左端）

所以我们递归地求解左右两边的最大子数组和，并计算跨越中点的最大子数组和，取三者中的最大值即可。

---

💻 C++代码实现 + 注释：

#include <iostream>
#include <vector>
#include <algorithm> // 用于 max 函数

using namespace std;

// 计算跨越中点的最大子数组和
int maxCrossingSum(const vector<int>& nums, int left, int mid, int right) {
    // 包含mid的左半部分最大和
    int leftSum = INT_MIN;
    int sum = 0;
    for (int i = mid; i >= left; --i) {
        sum += nums[i];
        leftSum = max(leftSum, sum);
    }

    // 包含mid+1的右半部分最大和
    int rightSum = INT_MIN;
    sum = 0;
    for (int i = mid + 1; i <= right; ++i) {
        sum += nums[i];
        rightSum = max(rightSum, sum);
    }

    // 返回跨越中点的总和
    return leftSum + rightSum;
}

// 分治法主函数
int maxSubArrayDivideAndConquer(const vector<int>& nums, int left, int right) {
    if (left == right) {
        // 只有一个元素时，直接返回
        return nums[left];
    }

    int mid = left + (right - left) / 2;

    // 三种情况取最大
    int maxLeft = maxSubArrayDivideAndConquer(nums, left, mid);          // 左边最大子数组和
    int maxRight = maxSubArrayDivideAndConquer(nums, mid + 1, right);    // 右边最大子数组和
    int maxCross = maxCrossingSum(nums, left, mid, right);               // 跨越中点的最大子数组和

    return max(max(maxLeft, maxRight), maxCross);
}

int main() {
    vector<int> nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};

    int result = maxSubArrayDivideAndConquer(nums, 0, nums.size() - 1);

    cout << "最大子数组和为：" << result << endl;

    return 0;
}

---

📝 输出结果：

最大子数组和为：6

---

⏱️ 时间复杂度分析：

• 分解：O(1)
• 解决：递归调用两个子问题 T(n/2)
• 合并：计算跨越中点的子数组和需要 O(n)

所以时间复杂度为：

$$T(n) = 2T\left(\frac{n}{2}\right) + O(n) \Rightarrow T(n) = O(n \log n) $$

---

🆚 对比 Kadane 算法（动态规划方法）

方法	时间复杂度	是否适合初学者	是否使用分治
分治法	O(n log n)	✅ 思路清晰	✅ 是
Kadane 算法	O(n)	✅ 更快更简单	❌ 不是分治

如果你正在学习分治算法，这个例子非常经典；如果只是追求效率，推荐使用 Kadane 算法（O(n)）。

---

📌 衍生题目建议练习：

1. LeetCode 53. Maximum Subarray
2. 最大子矩阵和
3. 循环数组的最大子数组和
4. 找出最大子数组的位置（起始和结束索引）

---

如需我为你讲解 Kadane 算法、或者拓展到最大子矩阵等问题，也可以继续提问哦 😊