CLRS 4.1.2-4.1.3 O(nlgn)

4.1.2findMaxSubarrsy.java

public static int[] findMaxSubArray(int[] A, int low, int high) {
	int[] result = new int[3];	
	
	if (high == low) {
		result[0] = low;
		result[1] = high;
		result[2] = A[low];
	} else {
		int mid = (low + high) / 2;
		int[] leftResult = findMaxSubArray(A, low, mid);
		int[] rightResult = findMaxSubArray(A, mid + 1, high);
		int[] crossResult = findMaxCrossingSubarray(A, low, mid, high);
		
		if (leftResult[2] >= rightResult[2] && leftResult[2] >= crossResult[2]) result = leftResult;
		else if (rightResult[2] >= leftResult[2] && rightResult[2] >= crossResult[2]) result = rightResult;
		else result = crossResult;
	}
	
	return result;
}
	
public static int[] findMaxCrossingSubarray(int[] A, int low, int mid, int high) {
	int[] result = new int[3];
	int leftSum = Integer.MIN_VALUE;
	int sum = 0;
	
	for (int i = mid; i >= low; i--) {
		sum = sum + A[i];
		if (sum > leftSum) {
			leftSum = sum;
			//max-left
			result[0] = i;
		}
	}
	
	int rightSum = Integer.MIN_VALUE;
	sum = 0;
	for (int j = mid + 1; j <= high; j++) {
		sum = sum + A[j];
		if (sum > rightSum) {
			rightSum = sum;
			//max-right
			result[1] = j;
		}
	}
	
	result[2] = leftSum + rightSum;
	return result;
}