4

发现很难理解两种 shot 和 k-shot 策略算法。这里又是一个问题：

Q1) arr 是一个长度为 n 的数组。计算 A[j0]-A[i0] + A[j1]-A[i1] 的最大值，条件是 i0 < j0 < i1 < j1

Ans）我们可以在 O(n) 中进行单次（即最大利润买卖股票）。我们可以应用相同的技术从 0..j 中找到最大值，从 j..n 中找到最大值。这将是 O(n2) 解决方案。

 Elements of Programming interviews book suggests a way of doing this in O(n) time by:
 doing a forward iteration and storing solution for A[0:j] such that 1<=j<=n-1  and then a backward iteration for A[j:n-1] such that 0<=j<=n-2 and then combining the two results.  Does anyone have any idea how this can be done?

Q2）你会怎么做k-shot？

谢谢！！

4

1 回答 1

3

第一季度

让我们首先解决这个更简单的问题O(n)：找到最大化的i0 < j0。A[j0] - A[i0]

对于每个j0，我们需要找到最小值0, 1, ..., j0 - 1并与A[j0] - this minimum全局最大值进行比较。到目前为止，这很容易通过计算最小值来完成。

现在，对于您的原始问题，我们还需要i1 < j1最大化A[j1] - A[i1]。或者，对于每个i1，我们需要找到j1 > i1最大化A[j1] - A[i1]的。

让：

min[i] = minimum in [0, ..., i]
max[i] = maximum in [i, ..., n - 1]

所以现在我们需要i < j最大化A[i] - min[i - 1] + max[j + 1] - A[j]。这可以通过计算来完成，在O(n)：

max1[i] = max{A[1] - min[0], A[2] - min[1], ..., A[i] - min[i - 1]}
max2[i] = max{max[i + 1] - A[i], max[i] - A[i - 1], ...max[1] - A[0]}

max1[i - 1] + max2[i]然后只取over all的最大值i >= 2。

于 2013-09-11T21:44:08.240 回答