算法导论（二）-------分治（D&C）思想之最大子数组问题

分治思想

在算法设计中分治思想在是一个十分重要的算法设计思想，我们可以在实际中多思考这种算法。这种算法主要时用函数的递归来进行实现的。主要的过程如下：
分： 将问题分为两个或者多个子问题
治 解决每一个子问题
合 最后自要将我们分开的子问题进行合并为我们需要解决的问题

比较官方的话就先写道这里了下面用实例来体会下这种思想

最大子（MCS）数组

定义：给我们一个数组

我们求出连续几个数和的最大值
例如：这九个数子的和为4
下标为1-5的这个子数组和为：2+1-4+5+2=6
小标为4–7的这个子数组和为：5+2-1+3=9（这个就是最大的子数组）
如果所有数组元素都是非负数，整个数组和肯定是最大

首先我们最容易想到的是暴力**直接上几个for循环记录下最大值。但是有没有更高效的算法呢？当然这就是我们的分治思想了。

理解

大致的递归函数为
我们传进来一个数组，我们从中间把这个数组分成两半，那么这个最大子数组一定是左半边的最大子数组或者最右边，再或者左右各有一部分的值，具体看下下面这张图：
如图当我们从中间进行分割的时候那么：
S1 = A[0…m]中的最大子数组
S2 = A[m+1…n]中的最大子数组
也可能这个最大子数组被切断了 在左边一半右边一半。
最大子数组的思想就是上面的这些

实战

首先我们先进行分析一下大致的过程来看下分治的具体过程
上面这是一个数组
从中间进行切开两半
按照这种切法一次递归。
最终为：

当我们进行分完之后我们下一步要进行治 如何来治呢 我们来仔细体会下：
当最终分为一个的时候需要返回

递归最后我们可以根据我们的分析来写相关的代码：
下面是我用C++来实现的注释很详细 大家应该可以看懂

#include<iostream>

using namespace std;

int MaxSubArray(int*,int,int);
int start = 0;
int endpos = 0;
int main()
{
	//先定义一个数据A
	int A[] = { -3,2,1,-4,5,2,-1,3,-1};
	int maxVlaue = MaxSubArray(A, 0, 8);
	cout << "最大值为：" << maxVlaue;
	getchar();
	return 0;
}

int MaxSubArray(int* A,int start,int end) {
	int Max = A[start];//默认最大值为第一个数字

	//进行递归的结束条件  当开始位置和结束位置一样的时候  只有一个数  我们不要递归下去了
	if (end - start == 1 || start == end) {
		return A[start] > A[end] ? A[start] : A[end]; //返回Max
	}
	// 从中间进行分开
	int mid = (start + end + 1) / 2;
	int AleftValue = MaxSubArray(A, start, mid);//进行查找左边的数字
	int ArightValue = MaxSubArray(A, mid, end);//查找右边的数字

	//然后进行查找可能包含中间的值的最大数组
	int midMaxValue = A[mid];
	int sum = A[mid];
	for (int i = mid - 1; i >= start; i--)
	{
		 sum += A[i];
		if (midMaxValue < sum)
		{
			midMaxValue = sum;
		}
	}
	sum = midMaxValue;
	for (int i = mid + 1; i < end + 1; i++)
	{
		sum += A[i];
		if (midMaxValue < sum)
		{
			midMaxValue = sum;
		}
	}
	//然后进行比较找出返回的最大值
	if (midMaxValue > AleftValue && midMaxValue > ArightValue)return midMaxValue;
	else if (AleftValue > midMaxValue && AleftValue > ArightValue) return AleftValue;
	else return ArightValue;
}

这就是分治算法的其中一个比较简单的应用大家可以试着写一下。在实验室无聊写的这个博客。做实验了…