ARTS （第20周）

开篇词

最近事情很多，但是生活和忙碌之余，也不能忘记学习。

本周：

动态规划

Algorithm 算法

最大有序子序列-动态规划



import java.util.Arrays;
import java.util.Random;

// 
public class DpLISTest {
	static Random rd = new Random();

	public static void main(String[] args) {

		while (true) {
			test();
		}
	}

	private static void test() {
		int s = 5;
		int[] n = new int[s];
		for (int i = 0; i < s; i++) {
			n[i] = rd.nextInt(9) + 1;
		}
		// n = new int[] { 8, 3, 6, 4, 8 };
		// n = new int[] { 8, 9, 1, 3, 3 };
		System.out.println("=-=-=-=-=-=-=");
		int r1 = lis(n);
		int r2 = maxSortNumsAll(n);
		System.out.println(Arrays.toString(n));
		System.out.println("r1:" + r1 + ",r2:" + r2);
		if (r1 != r2) {
			System.exit(0);
		}
	}

	/*
		
	*/
	// 简易版
	public static int lis(int[] a) {
		int[] dp = new int[a.length];
		for (int i = 0; i < a.length; i++) {
			dp[i] = 1;
			for (int j = 0; j < i; j++) {
				if (a[i] > a[j]) {
					// a[j]值为最大值的序列加上a[i]，所以进行加一
					int n1 = dp[j] + 1;
					// a[i]值为最大值的序列长度
					int n2 = dp[i];
					dp[i] = max(n1, n2);
				}
			}
		}
		// 找最大值
		int idx = 0;
		for (int i = 0; i < dp.length; i++) {
			if (dp[i] > dp[idx]) {
				idx = i;
			}

		}
		// 输出序列（只是其中一种）
		int ix = idx;
		System.out.print("->" + a[idx]);
		for (int i = idx - 1; i >= 0; i--) {
			// 其实可以用穷举 这里就不写了
			if (dp[i] + 1 == dp[idx]) {
				idx = i;
				System.out.print("," + a[idx]);
			}
		}
		System.out.println();
		return dp[ix];
	}

	// 复杂版
	public static int lis_(int[] a) {
		int[][] dp = new int[a.length][a.length];
		for (int i = 0; i < a.length; i++) {
			dp[i][i] = 1;
			// 复制一份
			for (int j = 0; j < i; j++) {
				dp[i][j] = dp[i - 1][j];
			}

			for (int j = 0; j < i; j++) {
				if (a[i] > a[j]) {
					// a[j]值为最大值的序列加上a[i]，所以进行加一
					int n1 = dp[i - 1][j] + 1;
					// a[i]值为最大值的序列长度
					int n2 = dp[i - 1][i];
					dp[i][i] = max(n1, n2);
				}
			}
		}
		// 找最大值
		int idx = 0;
		for (int i = 0; i < dp.length; i++) {
			if (dp[dp.length - 1][i] > dp[dp.length - 1][idx]) {
				idx = i;
			}

		}
		// 输出序列
		int ix = idx;
		System.out.print("->" + a[idx]);
		for (int i = idx - 1; i >= 0; i--) {
			// 其实可以用穷举 这里就不写了
			if (dp[dp.length - 1][i] + 1 == dp[dp.length - 1][idx]) {
				idx = i;
				System.out.print("," + a[idx]);
			}
		}
		System.out.println();
		return dp[dp.length - 1][ix];
	}

	public static int max(int n1, int n2) {
		if (n2 > n1) {
			return n2;
		}
		return n1;

	}

	

	public static int maxSortNumsAll(int[] n) {
		maxNums = 0;
		maxSortNumsAll(n, 0, 1, 1);
		return maxNums;
	}

	// 较慢
	public static int maxSortNumsAll_(int[] n) {
		maxNums = 0;
		maxSortNumsAll_(n, 0, 1, 1);
		return maxNums;
	}

	// 最大有序长度
	public static void maxSortNumsAll(int[] n, int i, int j, int len) {
		// System.out.println( "i=" + i + ",j=" + j );
		if (len > maxNums) {
			maxNums = len;
		}
		if (j == n.length) {
			return;
		}
		if (n[i] < n[j]) {
			// 有序度加一
			maxSortNumsAll(n, j, j + 1, len + 1);
		}
		// 跳过当前数
		maxSortNumsAll(n, i, j + 1, len);
		// 下一组数
		if (i == j - 1)// 少做点运算
			maxSortNumsAll(n, i + 1, j + 1, 1);
	}

	static int maxNums = 0;

	// 最大有序长度
	public static void maxSortNumsAll_(int[] n, int i, int j, int len) {
		// System.out.println( "i=" + i + ",j=" + j );
		if (len > maxNums) {
			maxNums = len;
		}
		if (j == n.length) {
			return;
		}

		// 当前数字和后续所有数字进行比较
		for (int k = j; k < n.length; k++) {
			if (n[i] < n[k]) {
				// 有序度加一
				maxSortNumsAll_(n, k, k + 1, len + 1);
			}
		}
		// 01 12 23
		maxSortNumsAll_(n, i + 1, j + 1, 1);
	}

	public static void printArr(int[][] arr) {
		System.out.println("----------------//");
		for (int[] is : arr) {
			System.out.println(Arrays.toString(is));
		}
		System.out.println("----------------//");
	}
	
	
}