本文共 1507 字，大约阅读时间需要 5 分钟。

最大子数组问题（递归）

作为分治策略的典型应用，时间复杂度可达到O(nlgn)，与归并排序相同。

分治策略应用三种步骤： 分解：将问题分解成子问题，子问题的形式跟原问题一样，但规模更小，如果所解决的问题不能够分解，则分治也无从谈起。 解决：不断递归，子问题被分解为更小规模的子问题，直到递归“触底”，这解决该问题，即停止递归，递归开始“上升”。 归并：将各子问题的解合成其父问题的解

以问题“最大子数组”为例：

分解：将数组“均匀”分为两半，原问题即分解为： 1：找出左半边数组的子数组的最大值 2：找出右半边数组的子数组的最大值 3：找出跨越中点的子数组的最大值 解决：当数组分解到只剩一个值的时候，此时其子数组的最大值即唯一元素，返回该元素，结束递归 归并：归并即将三种问题的解归并，在这里，则则是找出三种返回结果的最大值

该题如果加上限制条件：要求输出结果非负（即结果为负数时返回0）

可设计程序时间复杂度为O(n)，见函数getMax(int[] arr)

附代码：

public class LIANBIAO {
       public static void main(String[] args) {
            //int[] A = {13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7};        int[] A = {
   -7,-2,3,-4};        System.out.println(getMaxSubarray(A,0,A.length-1));        //System.out.println(getMax(a));    }        public static int  getMax(int[] arr){
           int len = arr.length;        int res = 0;        int max = 0;        for(int i=0;i
   
    max){
                   max = res;            }            //如果结果已经为负数            if(res<0){
                   res = 0;            }        }        return max;    }     //跨中点的最大子数组和的得出    public static int getMaxCrossarray(int[] A,int low,int mid,int high){
           int maxleft = Integer.MIN_VALUE;        int sumleft = 0;        for(int i=mid;i>=low;i--){
               sumleft+=A[i];            if(maxleft
    
     =rightMax&&leftMax>=crossMax){
               return leftMax;        }else if(rightMax>=leftMax&&rightMax>=crossMax){
               return rightMax;        }else{
               return crossMax;        }    }}
    
   

转载地址：http://dpfef.baihongyu.com/