实现内容：	假如有这样一个数组，A[] = {13,-2,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7};要求得到一个总值最大的子数组。例如A[]的一个最大子数组为A[7..10]={18,20,-7,12}。求解思想:	1）暴力求解		循环每一个元素，并从每一个元素的下标开始累加，每次选取较大的和。例如从第一个元素开始，第一次累加是13，那么记录最大的maxSubArray为13；第二次累加为13-2=11，比13小，maxSubArray还是为13；然后继续累加，选择最大的maxSubArray;最后循环下一个元素。A为输入数组，n为最大子数组起始元素下标,m为最大子数组终止元素下标,maxSum为最大子数组的和	   伪代码：	   FindMaxSubArray(A)	   maxSum=0	   for i = 1 to A.length	   		let curSum = 0	   		for j = i to A.length	   			curSum = curSum + A[j]	   			if curSum > maxSum	   				maxSum = curSum	   				let n = i,m = j	   return n,m,maxSum			2）分治思想		分治思想，把一个问题分解为很多小问题，先解决小问题然后再逐级向上解决整个问题。该问题的解决思想跟归并排序类似，先把数组拆分为两个子序列，然后两个子序列继续拆分。同样也需要一个辅助函数，用于计算子序列数组对应下标的最大子数组和。	   伪代码：		FindMaxCrossingSubArray(A,low,mid,high)  //辅助函数		left-sum = -∞		sum = 0		for i = mid down to low 			sum = sum + A[i]			if sum > left-sum				left-sum = sum				max-left = i		right-sum = -∞		sum = 0		for j = mid + 1 to high			sum = sum + A[j]			if sum > righ-sum				right-sum = sum				max-right = j		return (max-left,max-right,left-sum+right-sum)		FindMaxSubArrau(A, low, high) //主函数		if high == low 			return (low,high,A[low]) //分解为只有一个元素时		else			mid = (low+high)/2			(left-low,left-high,left-sum) = FindMaxSubArrau(A,low,mid)			(right-low,right-high,right-sum) = FindMaxSubArrau(A,mid+1,high)			(cross-low,cross-high,cross-sum) = FindMaxCrossingSubArray(A,low,mid,high)			if left-sum >= right-sum and left-sum >= cross-sum				return (left-low,left-high,left-sum)			else if right-sum >= left-sum and right-sum >= cross-sum				return (right-low,right-high,right-sum)			else 				return (cross-low,cross-high,cross-sum)	3）最优解		假如有这样一个数组，数组元素大于2并且数组元素里面有正负，那么最大子数组起始元素一定是正整数，每次从正整数开始计算，求出最大的子数组。i为最大子数组起始元素下标，j为最大子数组终止元素下标,maxSum为最大字数组的和	   伪代码：	   	FindMaxSubArray(A)  //注释的代码功能为记录最大子数组起始元素和终止元素的下标		flag = maxSum = curSum = 0		//i = j = 0;		for m = 0 to A.length			curSum = curSum + A[m]			if curSum > maxSum				//if flag != i				//	i = flag				//j = m				maxSum = curSum			if curSum < 0				curSum = 0				//if m < A.length-1				//	if A[m+1] > 0				//		flag = m + 1		//return i,j,maxSum 		return maxSum

　　

class FindMaxSubArray{	public static void main(String[] args) {		int[] A= {13,-2,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7};		//int[] A = {13,-2,-2,10};		//存放最大字数组的起始下标，终止下标，数组和		int[] result = new int[3];		//result = FindMaxSubArray1(A,result);		//result = FindMaxSubArray2(A,result,0,A.length-1);		result = FindMaxSubArray3(A,result);		for (int i: result) {			System.out.print(i+" ");		}	}	//暴力求解	public static int[] FindMaxSubArray1(int[] A,int[] result){		int i = 0, j = 0;		int maxSum = 0;		int len = A.length;		for (int m = 0;m < len; m++) {			int curSum = 0;			for (int n = m; n < len; n++) {				curSum += A[n];				if (curSum > maxSum){					maxSum = curSum;					i = m;					j = n;				}			}		}		getResult(result,i,j,maxSum);		return result;	}	//分治思想	public static int[] FindMaxSubArray2(int[] A,int[] result,int low,int high){		if(low==high){			result = getResult(result,low,high,A[low]);			return result;		}else{			int mid = (low+high)/2;			int[] leftResult = new int[3];			int[] rightResult = new int[3];			int[] crossResult = new int[3];			leftResult = FindMaxSubArray2(A,leftResult,low,mid);			rightResult = FindMaxSubArray2(A,rightResult,mid+1,high);				crossResult = FindMaxCrossingSubArray(A,crossResult,low,mid,high);						if(leftResult[2]>=rightResult[2]&&leftResult[2]>=crossResult[2]){				result = leftResult;				// System.out.print("left: ");				// for(int i:result){				// 	System.out.print(i+" ");				// }			}			else if (rightResult[2]>=leftResult[2]&&rightResult[2]>=crossResult[2]) {				result = rightResult;				//System.out.print("right: ");				// for(int i:result){				// 	System.out.print(i+" ");				// }			}else{				result = crossResult;				// System.out.print("cross: ");				// for(int i:result){				// 	System.out.print(i+" ");				// }			}			//System.out.println();			return result;		}	}	//分治过程中用到的辅助函数	public static int[] FindMaxCrossingSubArray(int[] A,int[] result,int low,int mid,int high){		int leftSum = A[mid];		int curLeftSum = 0;		int left = mid;		for(int i = mid; i >= low; i--){			curLeftSum += A[i];			if(curLeftSum > leftSum){				leftSum = curLeftSum;				left = i;			}		}		int rightSum = A[mid+1];		int curRightSum = 0;		int right = mid+1;		for(int i = mid+1; i <= high; i++){			curRightSum += A[i];			if(curRightSum > rightSum){				rightSum = curRightSum;				right = i;			}		}		result = getResult(result,left,right,leftSum+rightSum);		return result;	}	//最优解	public static int[] FindMaxSubArray3(int[] A,int[] result){		int m;		int i = 0;//记录起始元素的下标		int j = 0;//记录终止元素的下标		/*//记录 上一次maxSum最大时终止元素的下标		int k = 0;*/			int flag = 0;//记录curSum又一次从负整数变为正整数时起始元素的下标		int maxSum = 0;//最大子数组和		int curSum = 0;//当前最大子数组和		for (m=0;m
     
      maxSum){				//当前最大子数组和较大时，更换起始元素下标				if (flag != i) {					i = flag;				}				j = m;//更换当前终止元素下标				maxSum = curSum;				//更换上一次最大子数组终止元素的下标				/*if(k!=0||k!=j){					k++;				}				if ((j-k)!=1||j==0){					k = m;				}*/							}			if(curSum<0){				curSum = 0;				//记录下一个正整数为起始元素的下标				if (m<(A.length-1)) {					if (A[m+1]>0) {						flag = m+1;					}				}			}		}		result = getResult(result,i,j,maxSum);		return result;	}	public static int[] getResult(int[] result,int i,int j,int maxSum){		result[0] = i;		result[1] = j;		result[2] = maxSum;		return result;	}}