最大子數組問題的Java實作

《算法導論》的第四章：分治政策中提到了最大子數組問題。采用分治政策可以得到一個漸進複雜性優于暴力解法的算法。文中使用Java實作該算法。

問題：你被許可可以在某一時刻買進某公司的股票，并在之後某個日期将其賣出，買進賣出都是在當天交易結束後進行。為了補償這一限制，你可以了解股票将來的價格。你的目标是最大化收益。股票價格變化如下表：

天	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
價格	100	113	110	85	105	102	86	63	81	101	94	106	101	79	94	90	97
變化	——	13	-3	-25	20	-3	-16	-23	18	20	-7	12	-5	-22	15	-4	7

用Java實作算法，代碼如下：

public class Subarray {
	//如果最大子數組橫跨左右部分數組
	public static int[] FindMaxCrossingSubarray(int[] A, int low, int mid, int high) {
		int[] result = new int[3];
		//從中間點向左周遊，找出左半部分過中點的最大子數組
		int sum = 0;
		int i;
		for (i=mid;i>=low;i--) {
			sum = sum + A[i];
			if (sum>result[2]) {
				result[2] = sum;
				result[0] = i;
			}
		}
		//從中間往右周遊，找出右半部分過中點的最大子數組
		sum = 0;
		result[2] = 0;
		for (i=mid;i<=high;i++) {
			sum = sum + A[i];
			if (sum>result[2]) {
				result[2] = sum;
				result[1] = i;
			}
		}
		//将左右兩個子數組組合
		result[2] = 0;
		for (i = result[0];i<=result[1];i++) {
			result[2] = result[2] + A[i];
		}
		return result;
	}
	//将數組分成左右兩個部分，依次計算左數組、右數組的最大子數組，再計算橫跨左右部分的中間子數組，選擇最大的輸出
	public static int[] FindMaximumSubarray(int[] A, int low, int high) {
		int[] result = new int[3];
		int[] result_left = new int[3];
		int[] result_right = new int[3];
		int[] result_cross = new int[3];
		int mid = (int)(low+high)/2;
		//基本情況：數組中隻有一個元素，則傳回該數組
		if(low==high) {
			result[0]=low;
			result[1]=high;
			result[2]=A[low];
			return result;
		}
		//遞歸情況：數組中多于一個元素，依次計算三種情況下的最大子數組
		else {
			result_left = FindMaximumSubarray(A, low, mid);
			result_right = FindMaximumSubarray(A, mid+1, high);
			result_cross = FindMaxCrossingSubarray(A, low, mid, high);
			//比較三種情況的最大子數組，選擇最大的輸出
			if (result_left[2]>result_right[2] && result_left[2]>result_cross[2]) {
				return result_left;
			}
			else if (result_right[2]>result_left[2] && result_right[2]>result_cross[2]) {
				return result_right;
			}
			else {
				return result_cross;
			}
		}
	}
	public static void main(String[] args) {
		int[] result = new int[3];
		int[] A = {13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7};
		result = FindMaximumSubarray(A, 0, 15);
		System.out.print("The Maximum Subarray is : ");
		for(int i=result[0]; i<=result[1];i++) {
			System.out.print(A[i]+" ");
		}
		System.out.print("\nThe sum of the subarray is : "+result[2]);
	}
}
           

運作結果：

The Maximum Subarray is : 18 20 -7 12 
The sum of the subarray is : 43