伪代码

findMaxCrossingSubarray(A,low,mid,high) sum=0 leftSum=-9999//假设是无穷小 for i=mid downto low sum=sum+A[i] if sum>leftSum leftSum=sum maxLeft=i sum=0 rightSum=-9999 for j=mid+1 to high sum=sum+A[j] if sum>rightSum rightSum=sum maxRight=j return [maxLeft,maxRight,leftSum+rightSum] findMaximumSubArray(A,low,high) if low==high return [low,high,A[low]] else mid=floor((low+high)/2) [leftLow,leftHigh,leftSum]= findMaximumSubArray(A,low,mid) [rightLow,rightHigh,rightSum]= findMaximumSubArray(A,mid+1,high) [midLow,midHigh,midSum]= findMaxCrossingSubarray(A,low,mid,high) if(leftSum>=midSum and leftSum>=rightSum) return [leftLow,leftHigh,leftSum] else if(rightSum>=leftSum and rightSum>=midSum) return [rightLow,rightHigh,rightSum] else return [midLow,midHigh,midSum]

c语言实现

struct desc{ int a[3]; }x,y,leftX,midX,rightX; struct desc findMaxCrossingSubarray(int A[],int low,int mid,int hight){ int leftSum=-9999;//假设这是负无穷 int sum=0; int i,j; int maxLeft; for(i=mid;i>=low;i--){ sum=sum+A[i]; if (sum>leftSum){ leftSum=sum; maxLeft=i; } } int rightSum=-9999; sum=0; int maxRight; for(j=mid+1;j<=hight;j++){ sum=sum+A[j]; if(sum>rightSum){ rightSum=sum; maxRight=j; } } x.a[0]=maxLeft; x.a[1]=maxRight; x.a[2]=leftSum+rightSum; return x; //printf("最大子数组左坐标为:%d,最大子数组右坐标为：%d,最子数组的最大和为：%d",maxLeft,maxRight,leftSum+rightSum); } struct desc findMaximumSubArray(int A[],int low,int hight){ int mid; if(hight==low){ y.a[0]=low; y.a[1]=hight; y.a[2]=A[low]; return y; } else{ mid=floor((low+hight)/2); leftX=findMaximumSubArray(A,low,mid); rightX=findMaximumSubArray(A,mid+1,hight); midX=findMaxCrossingSubarray(A,low,mid,hight); if(leftX.a[2]>=rightX.a[2] && leftX.a[2]>=midX.a[2]) return leftX; else if(rightX.a[2]>=leftX.a[2] && rightX.a[2]>=midX.a[2]) return rightX; else return midX; } } void main(){ int A[]={1,-2,3,4,-5}; struct desc final=findMaximumSubArray(A,0,4); printf("最大子数组左坐标为:%d,最大子数组右坐标为：%d,最子数组的最大和为：%d",final.a[0],final.a[1],final.a[2]); }

java实现

public class Main { public static void main(String[] args) { int [] arr={1,-2,3,4,5}; List<Integer> finalDesc=findMaximumSubArray(arr,0,4); System.out.println("最大子数组左坐标为:"+finalDesc.get(0)+"\n最大子数组右坐标为:"+finalDesc.get(1)+"\n最大子数组的最大和为:"+finalDesc.get(2)); } public static List<Integer> findMaxCrossingSubArray(int [] arr,int low,int mid,int hight){ int sum=0; int leftSum=-9999; int maxLeft=0; for(int i=mid;i>=0;i--){ sum=sum+arr[i]; if(sum>leftSum){ leftSum=sum; maxLeft=i; } } sum=0; int rightSum=-9999; int maxRight=0; for(int j=mid+1;j<=hight;j++){ sum=sum+arr[j]; if(sum>rightSum){ rightSum=sum; maxRight=j; } } List<Integer> descList=new ArrayList<Integer>(); descList.add(maxLeft); descList.add(maxRight); descList.add(leftSum+rightSum); return descList; } public static List<Integer> findMaximumSubArray(int [] arr,int low,int hight){ List<Integer> descList=new ArrayList<Integer>(); int mid=0; if(low==hight){ descList.add(low); descList.add(hight); descList.add(arr[low]); return descList; } else { mid=(int)Math.floor((low+hight)/2); List<Integer> leftDesc=findMaximumSubArray(arr,low,mid); List<Integer> rightDesc=findMaximumSubArray(arr,mid+1,hight); List<Integer> midDesc=findMaxCrossingSubArray(arr,low,mid,hight); if(leftDesc.get(2)>=rightDesc.get(2) && leftDesc.get(2)>=midDesc.get(2)) return leftDesc; else if(rightDesc.get(2)>=leftDesc.get(2) && rightDesc.get(2)>=midDesc.get(2)) return rightDesc; else return midDesc; } } }