最大子数组

---

算法描述：

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 
    
     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};    }}