最大差值问题

发表于 更新于 分类于 本文字数： 367 阅读时长 ≈ 1 分钟

题目描述

有一个长度为n的数组A，求满足0 <= a <= b < n的A[b]-A[a]的最大值

思路

用到动态规划，假设f[i]表示前i个数组的最大值结果。f[i] 和 f[i - 1]比较就是要不要第i个数字。如果要，那么结果就是A[i] - (前i－1个数字中最小的)；如果不要，那就试f[i] - f[i - 1];这样状态方程就出来了。我们从最小情况i＝0出发，向上递增的同时更新前i－1中的最小值。

代码

1
2
3
4
5
6
7
8
9
int f[] = new int[n];
int min = a[0];
if (n > 1) {
	for (int i = 1; i != n; i++) {
		min = Math.min(min, a[i]);
		f[i] = Math.max(f[i -1], a[i] - min);
	}
}
return f[n - 1];