分割して治める方法——最大の子列と問題

//       

public class Practice_01{
	public static void main(String[] args) {
		int list[] = {4, -3, 5, -2, -1, 2, 6, -2};
		System.out.println("      ： " + DivideAndConquer(list, 0, list.length-1));
	}
	
	static int DivideAndConquer(int list[], int left, int right) {
		int MaxleftSum, MaxrightSum;  //      
		int MaxleftBorderSum, MaxrightBorderSum;  //      
		int leftBorderSum, rightBorderSum;
		int center;
		if(left == right) { //           ，      
			if(left > 0)
				return list[left];
			else
				return 0;
		}
		center = (left + right)/2;  //   
		MaxleftSum = DivideAndConquer(list, left, center);  
		MaxrightSum = DivideAndConquer(list, center+1, right);
		
		//          
		leftBorderSum = 0;
		MaxleftBorderSum = 0;
		for(int i=center; i >= left; i--) { //      
			leftBorderSum += list[i];
			if(leftBorderSum > MaxleftBorderSum)
				MaxleftBorderSum = leftBorderSum;
		}
		
		rightBorderSum = 0;
		MaxrightBorderSum = 0;
		for(int j=center+1; j <= right; j++) { //      
			rightBorderSum += list[j];
			if(rightBorderSum > MaxrightBorderSum)
				MaxrightBorderSum = rightBorderSum;
		}
		
		return maxofThree(MaxleftSum, MaxrightSum, MaxleftBorderSum + MaxrightBorderSum);
	}
	
	static int maxofThree(int A, int B, int C) {
		return A > B ? A > C ? A : C : B > C ? B : C;
	}
}