当前位置: 首页 > >

《算法法论学*笔记》-

发布时间:

最大子数组

算法描述:


1 找到数组中间位置mid,分成两个数组[low,mid],[mid,high]
2 最大子数组即为,[low,mid],[mid,high]和跨越mid的数组,3种情况之中的最大者。
3 [low,mid],[mid,high]可以使用递归算法求解
4 跨越中间点的情况,从中间点分别向左右遍历,寻找最大的包含中间点的最大子数组。将两者相加
5 比较[low,mid],[mid,high]和跨越mid的数组重的最大者即为所求




时间复杂度:

最大子段和即为这三个区间的最大子段和的最大值。因此原问题可化为两个求解规模为 n/2 的子问题,和求解一个跨越中点的序列的最大子段和问题。其中第三种情况可分别求解序列 a1,...,amida1,...,amid 和 amid+1,...,anamid+1,...,an 的最大子序列,然后将两者合并即可,因此该部分的时间复杂度为 Θ(n)。算法的时间复杂度可用递归的形式表示为:
T(n)={Θ(1),n=12T(n/2)+Θ(n),n>1
T(n)={Θ(1),n=12T(n/2)+Θ(n),n>1
可得,算法的复杂度为T(n)=Θ(nlgn)T(n)=Θ(nlgn)。




java 实现


import static java.lang.Float.POSITIVE_INFINITY;
/*
@Time? ? :2019/5/18 0018 下午 7:11
@Author? :喜欢二福的沧月君(necydcy@gmail.com)
@FileName: MaxCrossing.java
@Software: IntelliJ IDEA
*/
public class MaxCrossing {
/*
* 最大子数组:
* 分治法求解
* 1 找到数组中间位置mid,分成两个数组[low,mid],[mid,high]
* 2 最大子数组即为,[low,mid],[mid,high]和跨越mid的数组,3种情况之中的最大者。
* 3 [low,mid],[mid,high]可以使用递归算法求解
* 4 跨越中间点的情况,从中间点分别向左右遍历,寻找最大的包含中间点的最大子数组。将两者相加
* 5 比较[low,mid],[mid,high]和跨越mid的数组重的最大者即为所求
* */
public static void main(String[] args)
{
//测试函数
int[] array = { 9,10,8,12,6,10,12,11,9,1 };
int[] arr = new int[array.length-1];
for (int i = 0; i arr[i] = array[i+1]-array[i];
}
int[] result =FindMaxImumSubarray(arr, 0, arr.length - 1);
for (int value : result) {
System.out.println(value);
}
System.out.println("最大子字符串和:"+(array[result[0]]+array[result[1]]));
}

private static int[] FindMaxImumSubarray(int[] A, int low, int high) {

if (high == low){
return new int[]{low,high,A[low]};
}
else {
int mid = (low+high)/2;
int[] lefts = new int[3];
int[] mids = new int[3];
int[] rights = new int[3];
lefts = FindMaxImumSubarray(A,low,mid);
rights = FindMaxImumSubarray(A,mid+1,high);
mids = FindMaxCrossingSubarray(A,low,mid,high);
assert rights != null;
assert lefts != null;
if (lefts[2]>rights[2]&&lefts[2]>mids[2]){
return lefts;
}
else if (rights[2]>lefts[2]&&rights[2]>mids[2]){
return rights;
}
else return mids;
}
}

private static int[] FindMaxCrossingSubarray(int[] A, int low, int mid, int high) {
int leftSum = (int) -POSITIVE_INFINITY;
int sum = 0;
int maxLeft = 0;
for (int i = mid; i >=low ; i--) {
sum += A[i];
if (sum>leftSum){
leftSum = sum;
maxLeft = i;
}
}
int rightSum = (int) -POSITIVE_INFINITY;
sum = 0;
int maxRight = 0;
for (int j = mid+1; j <=high ; j++) {
sum += A[j];
if (sum>rightSum){
rightSum = sum;
maxRight = j;
}
}
return new int[]{maxLeft,maxRight,leftSum+rightSum};
}
}



转载于:https://www.cnblogs.com/miria-486/p/10887553.html






相关资源:2020年五一赛B题论文



友情链接: