系列算法计算内部最大下降？

Question

给定一个序列 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 的最佳算法是什么？

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

Answer 1

遍历系列，跟踪以下值:

• 到目前为止的最大元素
• 到目前为止的最大下降

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

• 还是一样
• 它等于maximumElementSoFar - newElement

所以选择一个给出更高值(value)的。迭代结束时的最大下降将是您的结果。这将在线性时间和恒定的额外空间内工作。