求最大子数组的JAVA源程序.docx

《求最大子数组的JAVA源程序.docx》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、publicclassMaximumSubarray{publicstaticint[]findMaxCossingSubarray(intA[],intlow,intmid,inthight){intleftsum=-0xffffff;intsum=0;intmaxlift=0;for(inti=mid;i>=low;i--){sum=sum+A[i];if(leftsum

2、(intj=mid+1;j<=hight;j++){sum=sum+A[j];if(rightsum

3、[]=newint[3];if(hight==low){result[0]=low;result[1]=hight;result[2]=A[low];returnresult;}else{intmid=(low+hight)/2;intleftresult[]=newint[3];leftresult=findMsximunSubarray(A,low,mid);intrightresult[]=newint[3];rightresult=findMsximunSubarray(A,mid+1,hight);intcoss

4、ingresult[]=newint[3];cossingresult=findMaxCossingSubarray(A,low,mid,hight);if(leftresult[2]>rightresult[2]&&leftresult[2]>cossingresult[2])returnleftresult;elseif(rightresult[2]>leftresult[2]&&rightresult[2]>cossingresult[2])returnrightresult;elsereturncossingres

5、ult;}}publicstaticvoidmain(String[]args){//intA[]={13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7};intA[]={-13,-3,-25,-20,-3,-16,-23,-18,-20,-7,-12,-5,-22,-15,-4,-7};intfinalresult[]={0,0,0};System.out.println("初始化是"+finalresult[0]+""+finalresult[1]+""+finalre

6、sult[2]);finalresult=findMsximunSubarray(A,0,A.length-1);System.out.println("结果是"+finalresult[0]+""+finalresult[1]+""+finalresult[2]);return;}}