分治策略（求最大子数组和）

大子数组和）"/>

分治策略（求最大子数组和）

思想：

1. 分治：将原问题分解为许多小问题，使小问题的形式与原问题相同，只是问题的规模更小。
2. 求解：递归地求解出子问题，当子问题的规模足够小时，停止递归，解决问题。
3. 合并：将子问题的解合并起来，组合成原问题的解。

例 求最大子数组和(leetcode 53T)

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组数组中的一个连续部分。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：
输入：nums = [1] 输出：1
示例 3：
输入：nums = [5,4,-1,7,8] 输出：23

---

求解nums[low,high]的最大子数组，根据分治策略，将原问题分解成同等形式的小问题，则可以以中间(mid)为标准进行分割，分成nums[low,mid] 和num [mid+1,high]两个子数组，然后对每个子问题以此类推，直至子问题不可再分。此种情况下，nums[low,high]中的最大连续子数组nums[i,j]必然为以下三种情况之一：

• 完全在 nums[low,mid]中
• 完全在nums[mid+1,high]中
• 跨越两个子数组，low < i < mid < j < high。

---

class Solution {
public:
int maxCrossSum(vector<int>& nums,int low,int mid,int high)
{int leftSum = -2147483648;int sum = 0;for(int i = mid;i >=low;i--){sum += nums[i];if(sum > leftSum){leftSum = sum;}}int rightSum = -2147483648;sum = 0;for(int i = mid + 1;i <=high;i++){sum += nums[i];if(sum > rightSum){rightSum = sum;}}return leftSum + rightSum;
}int maxLRSum(vector<int>& nums,int low,int high)
{if(low == high){return nums[low];}else{int mid = (low + high)/2;int leftArr = 0;leftArr = maxLRSum(nums,low,mid);int rightArr = 0;rightArr = maxLRSum(nums,mid + 1,high);int midArr = 0;midArr = maxCrossSum(nums,low,mid,high);if(leftArr >= rightArr && leftArr >= midArr){return  leftArr;}if(rightArr>= leftArr && rightArr >= midArr){return rightArr;}if(midArr>= leftArr&& midArr >= rightArr){return midArr;}}return 0;
}
int maxSubArray(vector<int>& nums) {int low = 0;int high = nums.size()-1;int sum = 0;sum = maxLRSum(nums,low,high);return sum;}
};