0

给定一个序列 x(i), i 从 1 到 N，假设 N = 10,000。

for any i < j,
D(i,j) = x(i) - x(j), if x(i) > x (j); or,
       = 0, if x(i) <= x(j).

定义

Dmax(im, jm) := max D(i,j), for all 1 <= i < j <=N.

计算 Dmax、im 和 jm 的最佳算法是什么？

我尝试使用动态编程，但这似乎不可分割......然后我有点迷茫......你们能建议吗？是回溯出路吗？

4

4 回答 4

2

遍历系列，跟踪以下值：

  • 迄今为止的最大元素
  • 迄今为止的最大下降

对于每个元素，新的最大下降有两个可能的值：

  • 它保持不变
  • 它等于maximumElementSoFar - newElement

所以选择价值更高的那个。迭代结束时的最大下降将是您的结果。这将在线性时间和恒定的附加空间中起作用。

于 2012-03-01T09:41:37.503 回答
0

如果我理解正确，您有一个数字数组，并且想要找到数组的两个相邻元素之间的最大正差？

由于您将不得不至少遍历一次数组来计算差异，我不明白为什么您不能一边走一边记录迄今为止发现的最大差异（以及它的位置），随着它的变化而更新。

如果你的问题和我理解的一样简单，我不确定你为什么需要考虑动态编程。我希望我误解了这个问题。

于 2012-03-01T09:39:19.113 回答
0

Dmax(im, jm) := max D(i,j) = max(x(i) -x(j),0) = max(max(x(i) -x(j)),0)

您只需要计算所有值的 x(i) -x(j)，即 O(n^2)，然后得到最大值。不需要动态规划。

于 2012-03-01T09:43:00.340 回答
0

您可以将系列 x(i) 划分为子系列，其中每个子系列包含 x(i) 的降序子列表（例如，如果 x = 5、4、1、2、1 则 x1 = 5、4、1 和 x2 = 2, 1) 然后在每个子列表中您可以执行以下操作： first_in_sub_series - last_sub_series 然后比较您获得的所有结果并找到最大值，这就是答案。

如果我正确理解了这个问题，这应该为您提供一个基本的线性算法来解决它。

例如：

x = 5, 4, 1, 2, 1 then x1 = 5, 4, 1 and x2 = 2, 1
rx1 = 4
rx2 = 1

dmax = 4 和 im = 1 和 jm = 3，因为我们谈论的是 x1，它是 x 的前 3 项。

于 2012-03-01T09:47:16.887 回答