//分治思想:先分再治
function maxSubSum(arr,left,right){
//console.log(right);
var leftMaxSum = rightMaxSum = 0;
//将这俩行代码放这里就会出错，是因为什么？
// var leftMaxBorderSum = rightMaxBorderSum = 0;
// var lefttemp = righttemp = 0;
if(left == right){
if(arr[left] > 0){
return arr[left];
}else{
return 0;
}
}
var center = Math.floor((left + right)/2);
var leftMaxSum = maxSubSum(arr,left,center);
var rightMaxSum = maxSubSum(arr,center+1,right);
//把代码放这里就不会出错，是因为什么？
var leftMaxBorderSum = rightMaxBorderSum = 0;
var lefttemp = righttemp = 0;
for(var i=center; i>=left; i--){
lefttemp += arr[i];
if(lefttemp >= leftMaxBorderSum){
leftMaxBorderSum = lefttemp;
}
}
for(var j=center+1; j<=right; j++){
righttemp += arr[j];
//console.log(j);
if(righttemp >= rightMaxBorderSum){
rightMaxBorderSum = righttemp;
}
}
console.log('['+left+','+right+']');
console.log(center+','+leftMaxSum+','+rightMaxSum+','+ (leftMaxBorderSum + rightMaxBorderSum));
return Math.max(leftMaxSum,rightMaxSum,(leftMaxBorderSum + rightMaxBorderSum));
}
var arr = [4,-3,5,-2,-1,2,6,-2];
console.log(maxSubSum(arr,0,7));
查看24道真题和解析
