2019-07-22 22:26

# 请求大佬支援！！想问问这个分治法的执行过程

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));
}
}
``````
• 写回答
• 好问题 提建议
• 关注问题
• 收藏
• 邀请回答