子数组最大合，时间nlog^n

package com.algorithm.complex;

public class SubMax {


public static void main(String[] args){

int[] a= {1,-87,8,66,-78,600,2};

System.out.println(subMax(a,0,a.length-1));
}

public static int subMax(int[] array,int left,int right){

if(left == right){

return array[left];
}
int model = (left+right)/2;

int leftmax = subMax(array,left,model);
int rightmax = subMax(array,model+1,right);
int leftbodermax = array[model]; int tmp=array[model];
for(int i = model-1 ;i >=left; i --){
tmp += array[i];

if(tmp>leftbodermax){
leftbodermax = tmp;}
}

int rightbodermax = array[model+1]; tmp = array[model+1];
for(int i = model+2; i <= right; i++ ){
tmp +=array[i];
if(rightbodermax<tmp){
rightbodermax = tmp;
}

}


int sum = rightbodermax + leftbodermax;
if(sum >leftmax && sum >rightmax){
return sum;
}
else if(leftmax >sum && leftmax >rightmax){
return leftmax;
}
else{
return rightmax;
}

}

}