最大子数组（最大子数组和）分治法 java代码实现（完整版）递归方式实现（分而治之）

什么是最大子数组：

子数组：数组中一段连续的序列
最大子数组：子数组中各个值相加和最大

一般人思维1:

蛮举，把数组中每个子数组都计算一遍
当然这样的算法效率是低下的

一般人思维2:

我们在蛮举的时候会发现其实有很多重复计算的地方，所以我们会想到保存上次相加后的结果，但是这样的算法效率也不够高，其时间复杂度为O(n²).
接下来我将会介绍用分而治之算法思想去解决问题

分而治之思维解决最大子数组问题：

什么是分而治之：

分而治之三步骤：分解原问题，解决子问题，合并问题解
1.分解原问题：将原问题分解为若干个规模较小，相对独立，与原问题形式相同的子问题。
2.解决子问：若子问题规模较小且易于解决时，则直接解。否则，递归地解决各子问题。
3.合并：将各子问题的解合并为原问题的解。

用在最大子数组问题上：

用分治法思维，如何分呢，我们可能会联想到归并排序的例子，（不太明白归并排序的读者可点击参考本人另一篇博客:归并排序），那我们能不能用到归并排序的递归思维去解决问呢，把他们划分为一个一个小片段，然后合并起来。
答案当然是可以的，我们可以在归并排序合并这一操作的时候把比较和交换移动步骤改为左半段求最大子数组和，右半段求最大子数组和，左半段和右半段结合起来求最大子数组和，而且我们会发现合并的时候都有左半段的右边和右半段的左边参与相加，考虑到这些，我们就很容易借鉴归并排序的递归思维去解决最大子数组问题。
用这种方法去解决问题时间复杂度能降到：O(nlogn).
如果你还没有看懂这些文字描述，可以结合本人在下面用java所写的代码进行分析，相信你会有所收获。

java完整代码实现（递归方式）：

public int toMaxSubarray(int []arr,int left,int right) {
	if(left >= right) {		  //递归出口
		return arr[left];
	}
	int mid = (left+right)/2;
	int leftMax = toMaxSubarray(arr, left, mid);			//左半段最大值
	int rightMax = toMaxSubarray(arr, mid+1, right);		//右半段最大值
	int mergeMax = addMaxSubarray(arr,left,mid,right);      //合并的最大值
	//返回三个数中最大的数
	return (leftMax=leftMax>rightMax?leftMax:rightMax)>mergeMax?leftMax:mergeMax; 
}
public int addMaxSubarray(int []arr,int left,int mid,int right) {
	int leftMax = (int) Double.NEGATIVE_INFINITY;
	int rightMax = (int) Double.NEGATIVE_INFINITY;
	for(int i = mid,sum = 0;i >= 0;i--) {	//左半边包含左半边右边元素的最大值
		sum = sum + arr[i];
		if(sum >= leftMax)
			leftMax = sum;
	}
	for(int j = mid+1,sum = 0;j <= right;j++) {
		sum = sum + arr[j];
		if(sum>rightMax)
			rightMax = sum;
	}
	int mergeMax = leftMax+rightMax;
	return mergeMax;
}


  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
 

调用函数及运行截图：

博客持续更新中，每天一篇算法博文，欢迎大家关注！

文章来源: blog.csdn.net，作者：Mr.Yushiwen，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/MrYushiwen/article/details/107203305