public class MaxSubSeqSum {
	/**
	 * 算法1，穷举搜索
	 */
	public static final int maxSubSeqSum1(int seq[]) {
		int length = seq.length;
		int sum = 0;
		for (int i = 0; i < length; i++) {
			for (int j = i; j < length; j++) {
				int theSum = 0;
				for (int k = i; k <= j; k++) {
					theSum += seq[k];
				}
				if (sum < theSum) sum = theSum;
			}
		}
		return sum;
	}
	
	/**
	 * 算法2，改进算法1
	 */
	public static final int maxSubSeqSum2(int seq[]) {
		int length = seq.length;
		int sum = 0;
		for (int i = 0; i < length; i++) {
			int theSum = 0;
			for (int j = i; j < length; j++) {
				theSum += seq[j];
				if (theSum > sum) {
					sum = theSum;
				}
			}
		}
		return sum;
	}
	
	/**
	 * 算法3：分治法
	 */
	public static final int maxSubSeqSum3(int seq[]) {
		return maxSubSeqSum31(seq, 0, seq.length - 1);
	}
	
	private static int max(int... args) {
		int max = Integer.MIN_VALUE;
		for (int i : args) {
			if (i > max) max = i;
		}
		return max;
	}
	
	private static final int maxSubSeqSum31(int[] seq, int left, int right) {
		if (right - left == 1) { // 只剩下两个了：
			return max(seq[left], seq[right], seq[left] + seq[right], 0);
		} else if (left == right) {
			return max(seq[left], 0);
		} else {
			int middle = (left + right) / 2;
			int maxLeft = maxSubSeqSum31(seq, left, middle);
			int maxRight = maxSubSeqSum31(seq, middle + 1, right);
			int maxMiddle = maxSubSeqMiddle(seq, left, right, middle);
			return max(maxLeft, maxRight, maxMiddle);
		}
	}
	
	private static final int maxSubSeqMiddle(int[] seq, int left, int right, int middle) {
		int maxLeft = 0, maxRight = 0;
		int temp = 0;
		for (int i = middle; i >= left; i--) {
			temp += seq[i];
			if (maxLeft < temp) {
				maxLeft = temp;
			}
		}
		temp = 0;
		for (int i = middle + 1; i <= right; i++) {
			temp += seq[i];
			if (maxRight < temp) {
				maxRight = temp;
			}
		}
		return max(maxLeft, maxRight, maxLeft + maxRight);
	}
	
	/**
	 * 最快的计算方式
	 * @param seq
	 * @return
	 */
	public static final int maxSubSeqSum4(int seq[]) {
		int sum = 0, theSum = 0;
		int length = seq.length;
		for (int i = 0; i < length; i++) {
			theSum = max(theSum + seq[i], 0);
			if (sum < theSum) {
				sum = theSum;
			}
		}
		return sum;
	}
	
	public static void main(String[] args) throws Exception {
		int length = 100000;
		int[] arr = new int[length];
		Random rand = new Random(10);
		for (int i = 0; i < length; i++) {
			arr[i] = rand.nextInt(11) - 5;
		}
		long t = System.currentTimeMillis();
//		int ret1 = maxSubSeqSum1(arr);
//		System.out.println("算法1耗时：" + (System.currentTimeMillis() - t));
//		System.out.println("结果1：" + ret1);
//		
		t = System.currentTimeMillis();
		int ret2 = maxSubSeqSum2(arr);
		System.out.println("算法2耗时：" + (System.currentTimeMillis() - t));
		System.out.println("结果2：" + ret2);
		
		t = System.currentTimeMillis();
		int ret3 = maxSubSeqSum3(arr);
		System.out.println("算法3耗时：" + (System.currentTimeMillis() - t));
		System.out.println("结果3：" + ret3);
		
		t = System.currentTimeMillis();
		int ret4 = maxSubSeqSum4(arr);
		System.out.println("算法4耗时：" + (System.currentTimeMillis() - t));
		System.out.println("结果4：" + ret4);
	}
}