欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-07-16 11:38:08
...

分治思想

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

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

最大子(MCS)数组

定义:给我们一个数组
算法导论(二)-------分治(D&C)思想之最大子数组问题
我们求出连续几个数和的最大值
例如:这九个数子的和为4
下标为1-5的这个子数组和为:2+1-4+5+2=6
小标为4–7的这个子数组和为:5+2-1+3=9(这个就是最大的子数组)
如果所有数组元素都是非负数,整个数组和肯定是最大

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

理解

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

实战

首先我们先进行分析一下大致的过程来看下分治的具体过程
算法导论(二)-------分治(D&C)思想之最大子数组问题上面这是一个数组
算法导论(二)-------分治(D&C)思想之最大子数组问题从中间进行切开两半
按照这种切法一次递归。
最终为:
算法导论(二)-------分治(D&C)思想之最大子数组问题
当我们进行分完之后我们下一步要进行 如何来治呢 我们来仔细体会下:
算法导论(二)-------分治(D&C)思想之最大子数组问题当最终分为一个的时候需要返回
算法导论(二)-------分治(D&C)思想之最大子数组问题算法导论(二)-------分治(D&C)思想之最大子数组问题
递归最后算法导论(二)-------分治(D&C)思想之最大子数组问题我们可以根据我们的分析来写相关的代码:
下面是我用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;
}

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