Class Code02_MaxLeftMaxRight

src/videocode/Code02_MaxLeftMaxRight.java:3–99

package videocode;

public class Code02_MaxLeftMaxRight {

	// 笨办法，但是好想
	public static int solution1(int[] arr) {
		if (arr == null || arr.length < 2) {
			return 0;
		}
		int N = arr.length;
		int ans = Integer.MIN_VALUE;
		// 0...0 左   1...N-1
		// 0...1 左   2...N-1 右
		// 0...2 左   3...N-1 右
		// 0...LeftEnd 左  leftEnd+1..N-1 右
		// 0...N-1    右无
		for (int leftEnd = 0; leftEnd < N - 1; leftEnd++) {
			int leftMax = arr[0];
			for (int i = 1; i <= leftEnd; i++) {
				leftMax = Math.max(leftMax, arr[i]);
			}
			int rightMax = arr[leftEnd + 1];
			for (int i = leftEnd + 2; i < N; i++) {
				rightMax = Math.max(rightMax, arr[i]);
			}
			ans = Math.max(ans, Math.abs(leftMax - rightMax));
		}
		return ans;
	}

	// 好办法，是我们真正想测试的
	public static int solution2(int[] arr) {
		if (arr == null || arr.length < 2) {
			return 0;
		}
		int N = arr.length;
		int max = arr[0];
		for (int i = 1; i < N; i++) {
			max = Math.max(max, arr[i]);
		}
		return max - Math.min(arr[0], arr[N - 1]);
	}

	// 生成随机数组arr
	// arr的长度也是随机决定的，为[0, maxLen]范围
	// arr的每个值也是随机决定的，为[-maxValue, +maxValue]范围
	// 最终返回arr
	public static int[] randomArray(int maxLen, int maxValue) {
		// Math.random()      ->   [O,1) 小数 等概率返回
		// Math.random() * N  ->   [0,N) 小数 等概率返回
		// (int)(Math.random() * N)  ->  [0,N-1] 整数 等概率返回
		// (int)(Math.random() * (N + 1)) -> [0,N] 整数 等概率返回
		// len ->  [0, maxLen] 整数，等概率
		int len = (int) (Math.random() * (maxLen + 1));
		int[] arr = new int[len];
		for (int i = 0; i < arr.length; i++) {
			// arr[i]    [-maxValue, +maxValue]
			arr[i] = 
					(int) (Math.random() * (maxValue + 1)) // [0, maxValue]
					-