2つのサブアレイの要素の最大絶対差

Question

配列を指定します。整数Kは、アレイを2つのサブアレイに分割します。 diffKは、max({A[0], A[1],....A[K]})- max({A[K+1],A[K+2],...A[n-1]})と定義されています。最大絶対値diifKを返します。時間の複雑さはO(n)で、最大スペースはcomplexity O(n)

Answer 1

です。アレイを通る1回のパスで、特定のインデックスから見える最大値を追跡する「ヘルパー」アレイを構築するのは簡単です。 （したがって、任意の所与Kため、helper[K] = max({A[0], A[1],....A[K]})。）

次いで、アレイを通る単一パス後方では、指定されたインデックス以降（Kインデックスであるmax({A[K+1],A[K+2],...A[n-1]})）から見た最大値を追跡することができ、そのインデックスの上記の "ヘルパー"配列の値と比較してください。同じインデックスの2つの値の間に表示される最大の差を追跡し、結果を返します。