package com.datastructures.capt0020;  
  
public class MaxSubSum {  
  
   
   
    private static int maxSumRec(int[] a, int left, int right){  
        if(left==right)//Base case  
            if(a[left]>0) return a[left];  
            else return 0;  
        int center = (left+right)/2;  
        int maxLeftSum=maxSumRec(a,left,center);  
        int maxRightSum=maxSumRec(a,center,right);  
          
        int maxLeftBorderSum = 0, leftBorderSum=0;  
        for(int i=center;i>=left;i--){  
            leftBorderSum+=a[i];  
            if(leftBorderSum>maxLeftBorderSum)  
                maxLeftBorderSum = leftBorderSum;  
        }  
        int maxRightBorderSum=0, rightBorderSum=0;  
        for(int i=center+1;i<=right;i++){  
            rightBorderSum+=a[i];  
            if(rightBorderSum>maxRightBorderSum)  
                maxRightBorderSum=rightBorderSum;  
        }  
        return maxLeftSum>maxRightSum?(maxLeftSum>(maxLeftBorderSum+maxRightBorderSum)?maxLeftSum:(maxLeftBorderSum+maxRightBorderSum))  
                                     :(maxRightSum>(maxLeftBorderSum+maxRightBorderSum)?maxRightSum:(maxLeftBorderSum+maxRightBorderSum));  
    }  
    /** 
     * Driver for divide-andconquer maximum contiguous 
     * subsequence sum algorithm. 
     * */  
      
    public static int getMaxSubSum3(int [] a){  
        return maxSumRec(a,0,a.length-1);  
    }  
      
  
    /** 
     * @param args 
     */  
    public static void main(String[] args) {  
        int [] a = {1,-1,0,2,9,-4,5,7,2,0};  
        System.out.println((0+a.length-1)/2);  
        System.out.println(1/2);  
          
//        //System.out.println(MaxSubSum.getMaxSubSum1(a));  
//        System.out.println(MaxSubSum.getMaxSubSum2(a));  
        System.out.println(MaxSubSum.getMaxSubSum3(a));  
//        System.out.println(MaxSubSum.getMaxSubSum4(a));  
        // TODO Auto-generated method stub  
  
    }  
  
}  

/*错误信息：
 * Exception in thread "main" java.lang.StackOverflowError
[color=#FF0000]    at com.datastructures.capt0020.MaxSubSum.maxSumRec(MaxSubSum.java:13)
    at com.datastructures.capt0020.MaxSubSum.maxSumRec(MaxSubSum.java:17)
    at com.datastructures.capt0020.MaxSubSum.maxSumRec(MaxSubSum.java:18)
    at com.datastructures.capt0020.MaxSubSum.maxSumRec(MaxSubSum.java:18)[/color]
 * */