0〜999の数字が厳密に増加する順番で配列があります。例えば間隔を最大にする番号を選択する
int[] array = {0, 24, 55, 124, 200, 259, 400, 503, 666, 797};
私は何をしているのは、これらの選んだ数字の間の距離の最小値が最大となるように、N個の数字を選ぶ機能を実装しています。
たとえば、Nが3の場合、選択された数値は0,400,797であり、間隔は400と397です。戻り値は397です（最大化する必要があります）。他の数値を選択すると、戻り値は397以下になります。
私は再帰を使用して実装したいと思いますが、それをコーディングするのは苦労しています。私を助けてくれませんか？
この問題は、dynamic programingを使用して解決できます。
c個の数字を選択し、最後に選択した数字を入力配列に持つインデックスpがある場合は、s[c][p]を解として定義するとします。私たちは、その後、状態、次の開始時s[c][p]
max for i=0..p of max(s[c-1][p-i], array[p] - array[p-i])ように計算することができ
：s[1][0..n]、nは、入力配列の長さで、値0を持つ必要があります。
s[1][0..n]を持つと、与えられた公式を使用してs[2][0..n]を簡単に計算できます。
s[2][0..n]を持つと、を簡単に計算できるようになりました。 nは、入力配列の長さであり、Nを選択する数字の数である
のように...
全体の問題を解決するには、max s[N][N-1..n]になり。
このソリューションの時間の複雑さはO(N*n^2)です。
説明：s[0..N][0..n]の値を計算します。各計算では、時刻の複雑さはO(n)です。
このソリューションのメモリの複雑さはO(n)です。
を計算するs[c][0..n]あなたはs[c-1][0..n]が必要なので、実際にはいつでもメモリの2*nが必要になります。
EDIT：再帰を使用して、memoization（https://en.wikipedia.org/wiki/Memoization）というプログラミング手法を使用して、前述のアルゴリズムを実装できます。
ありがとう！ :-) – 23thMay
@ 23thMay：あなたは歓迎です:) –
$ n $の上限はいくらですか？あなたはどんな複雑さを期待していますか？何を試しましたか？ – sashas
この問題は既に解決されています。次のスレッド[値の最小距離が最大になるようにサイズkのサブセットを検索する]を参照してください（http://stackoverflow.com/questions/22424885/find-subset-of-size-k-such-that-the-minimum -distance-between-values-is-maximum） –
Nが3の場合、最初の要素、最後の要素、中間点に最も近い要素を選択する必要があります。これはバイナリ検索であるため、O（log n）。 Nが高い場合は、同様のことがあります。 –