动态规划 - 最大子段跟

动态规划 - 最大子段和

给定一个数组A[A0,A1,A2,...,An]，求数组中连续子段之和的最大值。

(1)最简单的算法：穷举法

计算所有的连续子段之和，得出最大值

// 穷举法：计算所有的子序列和
// O(n^3)
public static int maxSum1(int[] data) {
	int max = data[0], tmp;
	for (int i = 0; i < data.length; i++) {
		for (int j = i; j < data.length; j++) {
			tmp = 0;
			for (int k = i; k <= j; k++) {
				tmp += data[k];
			}
			max = tmp > max ? tmp : max;
		}
	}

	return max;
}

(2) 穷举法改进版

去除

for (int k = i; k <= j; k++)

是的算法复杂度减为O(n^2)

// maxSum2的改进版
// O(n^2)
public static int maxSum2(int[] data) {
	int max = data[0], tmp;
	for (int i = 0; i < data.length; i++) {
		tmp = 0;
		for (int j = i; j < data.length; j++) {
			tmp += data[j];
			max = tmp > max ? tmp : max;
		}
	}

	return max;
}

(3) 动态规划

/**
 * M[j] = MAX(A[i]+A[i+1]+...+A[j])   i : 0~j
 * M[j] = M[j-1]+A[j]  M[j-1]>=0
 *      = A[j]         M[j-1]<0
 * max = MAX(M[j])   j : 0~n
 * M[j]是最后一项为A[j]的0~j之间的最大子段和，M的最大值即为最大子段和
 * O(n)
 */
public static int maxSum3(int[] data) {
	int[] M = new int[data.length];
	M[0] = data[0];
	for (int j = 1; j < data.length; j++) {
		if (M[j - 1] < 0) {
			M[j] = data[j];
		} else {
			M[j] += data[j];
		}
	}
	int max = M[0];
	for (int j = 1; j < M.length; j++) {
		if (max < M[j])
			max = M[j];
	}
	return max;
}

+最优子结构

整个数组的最大子项和，一定包含子数组的最大子项和。MAX(M[j])

+建立递归关系

自顶向下，建立递归关系，至最原子态的问题.

M[j] = M[j-1]+A[j] M[j-1]>=0
= A[j] M[j-1]<0

+自底向上，计算各个子问题的最优解

由最原子态的问题(M[0]=data[0])的最优解开始，构建全部子问题的最优解，并记录过程

+求解整个问题的最优解

由全部子问题的最优解，自顶向下，组合出整个问题的最优解

比较得出M的最大值。

(4)动态规划的改进版

/**
 * { 1, -2, 4, 10, -3, 5, 4, 6, 10, -30 }
 * max 1  1 4 14 14 16 20 26 36 36
 * tmp 1 -1 4 14 11 16 20 26 36 6
 * maxSum3的改进版，maxSum3中在最后寻找最大值，可改为在循环过程中只保存M的最大值
 */
public static int maxSum(int[] data) {
	int max = data[0], tmp = 0;
	for (int i = 0; i < data.length; i++) {
		if (tmp > 0) {
			tmp += data[i];
		} else {
			tmp = data[i];
		}

		if (max < tmp) {
			max = tmp;
		}
	}
	return max;
}

动态规划 - 最大子段跟

相关推荐