分治法里面的函数递归是如何执行的
maxSubArrayPart(nums,left,mid),
maxSubArrayPart(nums,mid+1,rig
ht),maxSubArrayAll(nums,left,mid,right)
这三个调用的结果是什么?
package com.student.play;
class Solution {
public static int maxSubArray(int[] nums) {
return maxSubArrayPart(nums,0,nums.length-1);
}
private static int maxSubArrayPart(int[] nums,int left,int right){
if(left==right){
return nums[left];
}
int mid=(left+right)/2;
return Math.max(
maxSubArrayPart(nums,left,mid),
Math.max(
maxSubArrayPart(nums,mid+1,right),
maxSubArrayAll(nums,left,mid,right)
)
);
}
//左右两边合起来求解
private static int maxSubArrayAll(int[] nums,int left,int mid,int right){
int leftSum=Integer.MIN_VALUE;
int sum=0;
for(int i=mid;i>=left;i--){
sum+=nums[i];
if(sum>leftSum){
leftSum=sum;
}
}
sum=0;
int rightSum=Integer.MIN_VALUE;
for(int i=mid+1;i<=right;i++){
sum+=nums[i];
if(sum>rightSum){
rightSum=sum;
}
}
return leftSum+rightSum;
}
public static void main(String args[]){
int nums[] = {-2,1,-3,4,-1,2,1,-5,4};
System.out.println(maxSubArray(nums));
}
}