分治法解决最大子数组问题
问题：输入一个整形数组（有正数也有负数），数组中连续的、一个或多个元素组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值。
输入：测试数组1, -2, 3, 10, -4, 7, 2, -5；
输出：最大子数组为3, 10, -4, 7, 2；
输出最大子数组的和为18 。
1.蛮力法求解
总体思路：
蛮力法是最简单的实现方法，只要列出数组所有可能的组合，然后找出其中和最大的组合即可；
蛮力法分三层循环实现：
1）第一层循环用于固定子数组的起始位置；
2）第二层循环用于确定子数组的结束位置；
3）第三层循环用于子数组和的计算，从子数组的头开始遍历到其尾，累加起来就是该子数组的和。
代码实现：
1 int ForseMax(int *arry,int n,int &_start,int &_end)
2 {
3 int i,j,k;
4 int sum;//用于求和
5 int _max=MIN;//记录最大和
6 for(i=0;i<n;i++)
7 {
8 for(j=i;j<n;j++)
9 {
10 sum=0;
11 for(k=i;k<j;k++)
12 {
13 sum+=arry[k];
14 }
15 if(sum>_max)
16 {
17 _start=i;//子数组开始处
18 _end=j;//子数组结尾处
19 _max=sum;
20 }
21 }
22 }
23 return _max;//返回最大和
24 }2.分治法求解
总体思路：
分治法的精髓：
1）分--将问题分解为规模更小的子问题；
2）治--将这些规模更小的子问题逐个击破；
3）合--将已解决的子问题合并，最终得出“母”问题的解；
所以原数组的最大子数组求法：
1）分--将原数组拆分成两部分，每个部分再拆分成新的两部分......直到数组被分得只剩下一个元素；
2）治--每个小型的数组找最大子数组，只有一个元素的数组，解就是该元素；
3）合--将两个小型数组合并为一个数组，其中解有三种可能：
-
-
- 左边的返回值大，
- 右边的返回值大，
- 中间存在一个更大的子数组和；
-
返回值应选最大的；
模块实现：
1 int Divide(int *arry,int l,int r)
2 {
3 if(l==r)//只有一个元素时，返回该元素
4 return arry[l];
5 else
6 {
7 int m=(l+r)/2;
8 int l_max=MIN,r_max=MIN,m_max=MIN;
9 l_max=Divide(arry,l,m);//左边和的最大值
10 r_max=Divide(arry,m+1,r);//右边和的最大值
11 m_max=MiddleMax(arry,l,r,m);//中间和的最大值
12 //返回三个值中最大的一个
13 if(l_max>=r_max && l_max>=m_max)
14 return l_max;
15 else if(r_max>=l_max && r_max>=m_max)
16 return r_max;
17 else
18 return m_max;
19 }
20 }难点解说：
其中难点在于两个数组合并的时候，位于两个数组中间位置存在最大和的情况，处理方法为：
从中间位置开始，分别向左和向右两个方向进行操作，通过累加找到两个方向的最大和，分别为l_max和r_max，因此存在于中间的最大和为（l_max+r_max）；
向左的累加操作和向右的累加操作完全一样，只需要一层循环就可以解决问题：
1）初始化l_max、r_max为最小值，命sum=0用于累加；
2）在向左累加的操作中，sum从中点开始向左逐个累加，累加完一个元素后与l_max相比，l_max保留值较大的一个；
3）等遍历完左边部分l_max的值得以确认，并用同样的方法确认r_max的值；
4）最后返回（l_max+r_max）的值。
具体代码实现如下：
1 int MiddleMax(int *arry,int l,int r,int m)
2 {
3 int l_max=MIN,r_max=MIN;//分别用于记录左、右方向累加的最大和
4 int i;
5 int sum;//用于求和
6 sum=0;
7 for(i=m;i>=l;i--)//中线开始向左寻找
8 {
9 sum+=arry[i];
10 if(sum>l_max)
11 l_max=sum;
12 }
13 sum=0;
14 for(i=m+1;i<r;i++)//中线开始向右寻找
15 {
16 sum+=arry[i];
17 if(sum>r_max)
18 r_max=sum;
19 }
20 return (l_max+r_max);//返回左右之和
21 }腾讯云开发者
