分治法解决最大子数组问题【转载】

最近在看《算法导论》，刚看到分治策略里的最大子数组问题，觉得这个写的不错，记录在这里，方便自己以后复习。

问题描述见《算法导论》P38

原文地址：https://www.cnblogs.com/Christal-R/p/Christal_R.html

代码如下：

 1 // 最大子数组分治法.cpp: 定义控制台应用程序的入口点。
 2 //
 3 
 4 #include "stdafx.h"
 5 #include <iostream>
 6 
 7 using namespace std;
 8 
 9 #define MIN -1000
10 
11 int MiddleMax(int *arry, int l, int r, int m)
12 {
13     int l_max = MIN, r_max = MIN;//分别用于记录左、右方向累加的最大和
14     int i;
15     int sum;//用于求和
16     sum = 0;
17     for (i = m; i >= l; i--)//中线开始向左寻找
18     {
19         sum += arry[i];
20         if (sum>l_max)
21             l_max = sum;
22     }
23     sum = 0;
24     for (i = m + 1; i<r; i++)//中线开始向右寻找
25     {
26         sum += arry[i];
27         if (sum>r_max)
28             r_max = sum;
29     }
30     return (l_max + r_max);//返回左右之和
31 }
32 
33 int Divide(int *arry, int l, int r)
34 {
35     if (l == r)//只有一个元素时，返回该元素
36         return arry[l];
37     else
38     {
39         int m = (l + r) / 2;
40         int l_max = MIN, r_max = MIN, m_max = MIN;
41         l_max = Divide(arry, l, m);//左边和的最大值
42         r_max = Divide(arry, m + 1, r);//右边和的最大值
43         m_max = MiddleMax(arry, l, r, m);//中间和的最大值
44                                          //返回三个值中最大的一个
45         if (l_max >= r_max && l_max >= m_max)
46             return l_max;
47         else if (r_max >= l_max && r_max >= m_max)
48             return r_max;
49         else
50             return m_max;
51     }
52 }
53 
54 int main()
55 {
56     int a[] = {13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7};
57     int b[] = { -1,-2,-3,-4,-5,-6,-7,-8,-9 };
58     cout << Divide(a, 0, 15) << endl;
59     return 0;
60 }

运行结果如下：

分治法解决最大子数组问题【 转载】

分治法解决最大子数组问题【转载】