\(^_^)/ 最大子序列和的问题求解

参考：http://blog.163.com/lichunliang1988116@126/blog/static/2659944320124115795/

参考：http://blog.csdn.net/sgbfblog/article/details/8032464

参考：http://blog.csdn.net/luxiaoxun/article/details/7438315

 

 

 

import java.util.Random;

public class SubSequence {
	public static void main(String[] args) {
		int[] array = new int[10000];
		Random random = new Random();
		for (int i = 0; i < array.length; i++) {
			array[i] = random.nextInt(1000);
		}
		long start = System.currentTimeMillis();
		System.out.println(maxSubSequence1(array));
		long end = System.currentTimeMillis();
		System.out.println("Cost:" + (end - start));

		start = System.currentTimeMillis();
		System.out.println(maxSubSequence2(array));
		end = System.currentTimeMillis();
		System.out.println("Cost:" + (end - start));

		start = System.currentTimeMillis();
		System.out.println(maxSubSequence3(array, 0, array.length - 1));
		end = System.currentTimeMillis();
		System.out.println("Cost:" + (end - start));

		start = System.currentTimeMillis();
		System.out.println(maxSubSequence4(array));
		end = System.currentTimeMillis();
		System.out.println("Cost:" + (end - start));
	}

	public static int maxSubSequence1(int[] array) {
		int maxSum = 0;
		for (int i = 0; i < array.length; i++) {
			for (int j = i; j < array.length; j++) {
				int tempSum = 0;
				for (int k = i; k <= j; k++) {
					tempSum += array[k];
				}
				if (tempSum > maxSum) {
					maxSum = tempSum;
				}
			}
		}
		return maxSum;
	}

	public static int maxSubSequence2(int[] array) {
		int maxSum = 0;
		for (int i = 0; i < array.length; i++) {
			int tempSum = 0;
			for (int j = i; j < array.length; j++) {
				tempSum += array[j];
				if (tempSum > maxSum) {
					maxSum = tempSum;
				}
			}
		}
		return maxSum;
	}

	public static int maxSubSequence3(int[] array, int left, int right) {
		if (left == right) {
			if (array[left] > 0) {
				return array[left];
			} else {
				return 0;
			}
		} else {
			int center = (left + right) / 2;
			int maxLeftSum = maxSubSequence3(array, left, center);
			int maxRightSum = maxSubSequence3(array, center + 1, right);

			int maxLeftBorderSum = 0, leftBorderSum = 0;
			for (int i = center; i >= left; i--) {
				leftBorderSum += array[i];
				if (leftBorderSum > maxLeftBorderSum) {
					maxLeftBorderSum = leftBorderSum;
				}
			}

			int maxRightBorderSum = 0, rightBorderSum = 0;
			for (int i = center + 1; i <= right; i++) {
				rightBorderSum += array[i];
				if (rightBorderSum > maxRightBorderSum) {
					maxRightBorderSum = rightBorderSum;
				}
			}

			int max = maxLeftSum;
			if (max < maxRightSum) {
				max = maxRightSum;
			}
			if (max < maxLeftBorderSum + maxRightBorderSum) {
				max = maxLeftBorderSum + maxRightBorderSum;
			}
			return max;
		}
	}

	public static int maxSubSequence4(int[] array) {
		int maxSum = 0, tempSum = 0;
		for (int i = 0; i < array.length; i++) {
			tempSum += array[i];
			if (tempSum > maxSum) {
				maxSum = tempSum;
			} else if (tempSum < 0) {
				tempSum = 0;
			}
		}
		return maxSum;
	}

}