共计 5346 个字符，预计需要花费 14 分钟才能阅读完成。
本文首发自「慕课网」，想理解更多 IT 干货内容，程序员圈内热闻，欢送关注！
作者 | 慕课网精英讲师 JdreamZhang
最大子数组（Max Subarray）问题，是计算机科学与技术畛域中一种常见的算法问题，次要能够利用分治思维进行疾速实现。最大子数组问题形容如下：如果咱们有一个数组，数组中的元素有负数和正数，如何在数组中找到一段间断的子数组，使得子数组各个元素之和最大。最大子数组问题在生活中有很多理论状况能够与其对应，比如说咱们察看某一股票在一段时间内的走势，请问如何找出在哪一天买入，哪一天卖出能够赚到最大差价（这里假如你曾经晓得股票的价格走势）？
为了实现最大化的股票收益，咱们须要思考的是买进和卖出时候的价格变动幅度，因而从该股票的每日变动幅度来思考这个问题更加适合。所以，咱们能够将这个问题稍作变形：将股票价格走势对应为每日股票价格涨跌，涨记为正值，跌记为负值，而后一段时间就对应一个正负数数组，并试图找到该数组的最大子数组，就能够取得最大收益。接下来，就让咱们看看如何利用分治算法求解最大子数组问题吧。1. 分治法求解最大子数组问题在最大子数组问题之后，咱们一起来看一下如何利用分治思维求解最大子数组问题。这里咱们假如待初始的数组为 [12, -3, -16, 20, -19, -3, 18, 20, -7, 12, -9, 7, -10]，记为数组 A，并用 A [low,high] 示意这个数组，其中 low，high 是这个数组的最小最大下标，low = 0，high = A.length -1 , 而后咱们须要找到该数组的其中某一个最大子数组。Tips: 这里咱们须要留神，同一数组的最大子数组可能有多个，所以咱们在这里求解的时候只说求解某一个最大子数组。1.1 分治算法求解思路在这里，咱们用分治算法求解最大子数组问题，次要思路如下：步骤 1：找到数组 A 的两头元素，其下标记为 mid，依据分治策略，将数组 A [low,high] 依据两头元素划分为 A [low,mid]，A [mid+1,high] 两个局部；步骤 2：假如数组 A 的最大子数组为 A [i, j]，那么 A [i, j] 只有以下三种可能：a: 最大子数组 A [i, j] 齐全位于 A [low, mid] 中，此时有 low <= i <= j <= mid;b: 最大子数组 A [i, j] 齐全位于 A [mid+1, high] 中，此时有 mid+1 <= i <= j <= high;c: 最大子数组 A [i, j] 跨域了两头元素，则 low <= i <= mid <= j <= high。别离计算上述三种对应的最大子数组的后果；Tips: 在这里，状况 a 和状况 b 这两种状况所得的子问题和之前求解数组 A 的最大子数组的问题模式齐全一样，这里是分治思维的次要体现，将大的问题拆分成了两个雷同模式的小问题；状况 c 这时候能够间接求解，在 3.2 节中会具体介绍其求解过程。步骤 3 对步骤 2 三种状况的求解后果进行比拟，其中最大子数组的后果为最大值的状况就是咱们的所求后果。1.2 求解思路详解首先，咱们将 3.1 节中的求解思路用下图示意：
如图，咱们能够更分明地明确求解一个数组的最大子数组问题就是对 1.1 节中的步骤 2 中的三种状况的别离求解，步骤 2 中的状况 a 和状况 b 能够通过递归求解得出后果，所以咱们当初先看一下状况 c 的具体求解过程。状况 c 的求解很容易在线性工夫内就能够得出后果，他并不是原问题的一个规模更小的实例，因为状况 c 中退出了一个限度（求出的子数组必须逾越下标为 mid 的两头节点）。如上图的左边图形所示，状况 c 的求解后果都会有两个子数组 A [i,mid] 和 A [mid+1,j] 组成，其中 low <= i <= mid <= j <=high。因而，咱们只须要找出形如 A [i,mid] 和 A [mid+1,j] 的最大子数组，而后将其合并即可。咱们用上面的伪代码 FindMaxCrossSubarray 形容 1.1 节中 步骤 2 中的状况 c 具体实现过程：FindMaxCrossSubarray(A, low, mid ,high):
leftSum = minInteger; // 设置右边的最大间断和初始值为最小整数值
sum =0;
maxLeft = mid; // 记录右边最大子数组的下标地位, 初始化为 mid
for (i=mid; i>=low; i–){
sum = sum + A[i];
if (sum > leftSum){
leftSum = sum;
maxtLeft = i;
}}
rightSum = minInteger; // 设置左边的最大间断和初始值为最小整数值
sum = 0;
maxtRight = mid + 1; // 记录左边最大子数组的下标地位, 初始化为 mid+1
for (j=mid+1; j<=low; j++){
sum = sum + A[j];
if (sum > rightSum){
rightSum = sum;
maxtRight = j;// 记录右边最大子数组的下标地位
}}
// 返回后果是一个三元组数据，别离是最大子数组的开始下标，完结下标，求和的值
return (maxLeft,maxRight,leftSum+rightSum);
代码块 1234567891011121314151617181920212223 上述伪代码的形容中的第 2 至第 11 行，是求解左半局部 A [low,mid] 的最大子数组的过程，因为必须蕴含下标为 mid 的元素，所以从下标为 mid 的两头节点开始逐渐递加到下标为 low 的元素，对应伪代码中的第 5 至第 11 行的 for 循环构造，循环的过程中会记录下右边局部的最大子数组的具体值及左半局部的下标地位。同理，上述伪代码的第 12 至第 21 行对应的是求解右半局部 A [mid+1,high] 的最大子数组的过程。最初，伪代码中的第 23 行综合左右两边求解后果，返回必须逾越下标为 mid 的两头元素时，对应的原数组 A 的最大子数组后果。当咱们能够分明地晓得步骤 2 中的状况 c 的求解过程时，咱们就能够综合晓得对于数组 A 求解最大子数组的整体过程，用伪代码 FindMaxSubarray 形容如下：FindMaxSubarray(A,low,high):
if (high == low){return new Result(low,high,A[low]); // 根底状况，只有一个元素时候的解决状况
}else {
// 对应 2.1 节中步骤 1，找到两头元素
int mid = (low + high)/2;
// 对应 2.1 节中步骤 2，别离对应 a,b,c 三种状况求解最大子数组后果
(leftLow,leftHigh,leftSum) = FindMaxSubarray(A,low,mid);
(rightLow,rightHigh,rightSum) = FindMaxSubarray(A,mid+1,high);
(crossLow,crossHigh,crossSum) = FindMaxCrossSubarray(A,low,mid,high);
// 对应 2.1 节中步骤 3，比拟得出最初后果
if(leftSum >= righSum && leftSum >= crossSum){return (leftLow,leftHigh,leftSum);
}else if (rightSum >= leftSum && rightSum >= crossSum){return (rightLow,rightHigh,rightSum);
}else {return (crossLow,crossHigh,crossSum);
}
}代码块 12345678910111213141516171819 上述求解数组 A 的最大子数组的整体过程伪代码，次要就是由咱们在 1.1 节中形容的三大步骤而来。代码第 2 至第 4 行，次要表明了最根底的状况的解决形式。代码第 4 至第 18 行对应着具体的实现形式，第 8 行和第 9 行别离是对子问题的递归求解，第 10 行调用 FindMaxCrossSubarray 过程，求解逾越两头节点的最大子数组求解形式，最初第 12 至 18 行比照三种状况的后果得出最终后果。2.JAVA 代码实现在阐明求解最大子数组的整个过程之后，接下来，咱们看看如何用 java 代码实现最大子数组问题的求解。package divide_and_conquer;
public class MaxSubarray {
// 外部类，用来存储最大子数组的返回后果，private static class Result {
int low;
int high;
int sum;
public Result(int low, int high, int sum) {
this.low = low;
this.high = high;
this.sum = sum;
}
@Override
public String toString() {
return "Result{" +
"low=" + low +
", high=" + high +
", sum=" + sum +
'}';
}
}
private static Result FindMaxCrossSubarray(int[]A,int low, int mid, int high){
// 寻找右边的间断最大值及记录地位
int leftSum = Integer.MIN_VALUE;
int sum = 0;
int maxLeft = mid;
for (int i=mid; i>=low; i--){sum = sum + A[i];
if(sum > leftSum){
leftSum = sum;
maxLeft = i;
}
}
// 寻找左边的间断最大值及记录地位
int rightSum = Integer.MIN_VALUE;
int maxRight = mid+1;
sum = 0;
for (int j=mid+1; j<=high;j++){sum = sum + A[j];
if(sum > rightSum){
rightSum = sum;
maxRight = j;
}
}
// 返回逾越两头值的最大子数组后果
return new Result(maxLeft,maxRight,leftSum + rightSum);
}
public static Result FindMaxSubarray(int[] A, int low, int high){
// 数组只有一个元素时的解决状况
if (high == low){return new Result(low,high,A[low]);
}else {
// 对应思路中步骤 1，找到两头元素
int mid = (low + high)/2;
// 对应思路中步骤 2，别离对应 a,b,c 三种状况求解最大子数组后果
Result leftResult = FindMaxSubarray(A,low,mid);
Result rightResult = FindMaxSubarray(A,mid+1,high);
Result crossResult = FindMaxCrossSubarray(A,low,mid,high);
// 对应步骤 3，比拟
if(leftResult.sum >= rightResult.sum && leftResult.sum >= crossResult.sum){return leftResult;}else if (rightResult.sum >= leftResult.sum && rightResult.sum >= crossResult.sum){return rightResult;}else {return crossResult;}
}
}
public static void main(String[] args){int[] A = {12, -3, -16, 20, -19, -3, 18, 20, -7, 12, -9, 7, -10};
System.out.println(FindMaxSubarray(A,0,A.length-1).toString());
}}
代码块 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384 运行后果如下：Result{low=6, high=9, sum=43}
代码块 1 运行后果中的 low 示意最大子数组在数组 A 中的开始下标，high 示意最大子数组在数组 A 中的终止下标，sum 示意最大子数组的求和值，对应到咱们的实例数组 A 中，对应的最大最大子数组为 [18,20,-7,12]。代码中第 5 行至 25 行的 Result 外部类，次要是用来存储最大子数组的返回后果，定义了子数组的开始下标，完结下标，求和值。代码的第 27 至 55 行是最大子数组逾越两头节点时候的最大子数组求解过程。代码的第 58 至 78 行是整个最大子数组的求解过程。代码的第 81 行和 82 行是求解最大子数组过程的一个示例，输入最大子数组的求解后果。3. 小结本篇文章次要利用分治思维求解最大子数组问题，须要大家充沛相熟理解分治算法的算法流程，晓得分治算法在解决最大子数组时的实现思路，能够本人用代码实现最大子数组问题的求解。这次咱们通过最大子数组这一实例介绍了分治算法的理论利用，心愿能够帮忙大家更好地了解分治算法。
欢送关注「慕课网」，发现更多 IT 圈优质内容，分享干货常识，帮忙你成为更好的程序员！
