算法实践篇-求最大子数组

算法实践篇-求最大子数组

package com.sort.divid;/** * 求最大子数组 * @author Administrator *nlogn */public class MaxSubArray { private static int[] findMaxCrossSubArray(int [] data,int left,int middle,int right){ int [] result=new int[3]; int leftmax=data[middle]; int sum=leftmax; int leftIndex=middle; for(int i=middle-1;i>=left;i--){ sum=sum+data[i]; if(sum>leftmax){ leftmax=sum; leftIndex=i; } } int rightmax=data[middle+1]; sum=rightmax; int rightIndex=middle+1; for(int i=middle+2;i<=right;i++){ sum=sum+data[i]; if(sum>rightmax){ rightmax=sum; rightIndex=i; } } result[0]=leftmax+rightmax; result[1]=leftIndex; result[2]=rightIndex; return result; } private static int[] findMaxSubArray(int []data,int left,int right){ int [] result=new int[3]; if(left==right){ result[0]=data[left]; result[1]=left; result[2]=right; return result; } int middle=(left+right)/2; int[] leftResult=findMaxSubArray(data,left,middle); int [] rightResult=findMaxSubArray(data,middle+1,right); int []crossResult=findMaxCrossSubArray(data,left,middle,right); if(leftResult[0]>rightResult[0]&&leftResult[0]>crossResult[0]){ return leftResult; }else if(rightResult[0]>leftResult[0]&&rightResult[0]>crossResult[0]){ return rightResult; }else{ return crossResult; } } public static void main(String[] args) { int[] data=new int[]{-1,2,9,11,-20,9,6,22,-8,9,1}; for(int i=0;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。