leetcode 分治策略最大子数组问题

分三种情况： 1.完全位于nums[start,mid]中 ， 因此start <= i <= j <= mid; 2.完全位于nums[mid+1 , end]中,因此mid < i <= j <=end 3.跨越了中点 ， 因此start <= i <= mid <= j <= end;

class Solution { public int maxSubArray(int[] nums) { return megreMax(nums , 0 , nums.length - 1); } public int megreMax(int [] nums , int start , int end){ if(start == end){ return nums[start]; }else{ int mid = start + ((end - start) >> 1); int lnSUm = megreMax(nums , start , mid); int rnSum = megreMax(nums , mid + 1 , end); int sum = getmax(nums , start , mid , end); if(lnSUm >= rnSum && lnSUm >=sum) return lnSUm; else if(rnSum >= lnSUm && rnSum >= sum) return rnSum; else return sum; } } public int getmax(int [] nums , int start ,int mid,int end){ int lnSum = -Integer.MAX_VALUE; int lnNum = 0; for(int i = mid ; i >= start ; --i){ lnNum = lnNum+nums[i]; if(lnNum > lnSum){ lnSum = lnNum; } } int rnSum = -Integer.MAX_VALUE; int rnNum = 0; for(int j = mid + 1 ; j <= end ; ++j){ rnNum = rnNum + nums[j]; if(rnNum > rnSum){ rnSum = rnNum; } } return lnSum+rnSum; } }