4

ツー ショット戦略アルゴリズムと k ショット戦略アルゴリズムを理解するのは難しいと思います。ここでまた質問です：

Q1) arr は長さ n の配列です。i0 < j0 < i1 < j1 という条件に従って、A[j0]-A[i0] + A[j1]-A[i1] の最大値を計算します

回答) O(n) でシングルショット (つまり、最大利益の売買株) を実行できます。同じ手法を適用して、0..j から max を見つけ、j..n から max を見つけることができます。それは 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

Q1

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 > i1A[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]すべての最大値を取りますi >= 2。

于 2013-09-11T21:44:08.240 に答える