いくつかの単純なロジックのヘルプが必要です。数時間の間スタックされました。

Question

問題は、任意の数の数値を取って、連続する数字間の差（絶対値を使用して）の最大可能な和を求めています。例えば、数字1,2および3は、合計3（3-1 = 2、および1-2 = 1）を得るために3 1 2に配置される。

私の最初の考えは、リストの中で最も高い数字とそれに続く数字の順番で並んでいますが、リストの最後がすべての数字真ん中にはほとんど違いがない。私が考えている唯一の他のものは、すべての可能な順序を見つけて最高額を返すことですが、リストが長くなるとこれは長くなりすぎ、よりよい方法があると思います。そのだけで正しい方向に私を指している場合でも、参考のために

は、ここでは、

9 2 5 3 1 -> 21 
7 3 4 5 5 7 6 8 5 4 -> 24 

全くすべてのヘルプははるかに高く評価されるだろういくつかのサンプルの入力と出力の数です。

Answer 1

この問題には2つのアプローチがあります。

アプローチ1：

ブルートフォース。

アプローチ2：

図外の数字を整理する方法のためのアルゴリズム。

実現可能であれば、私は常にアプローチ2がより好きです。

とても数字をソートすることによって開始し、2つの均等に大きなグループに分割する

...あなたは高低高低高の数字を注文する場合は、高合計になるだろうという合理的なようです低い数字と高い数字の奇数の数字がある場合、中間の数字が残されます。

次に、2つのグループから番号を交互に選択します。

高低の低い注文にこだわる限り、内装番号の順序は問題ではないことを証明するのは簡単です。 ただし、開始番号と終了番号には1つのネイバーしかないため、最初と最後の番号は中間の番号にする必要があります。

最後に、奇数の数字がある場合は、最も大きな違いがあれば、最後または最後の数字を先頭または末尾に置きます。

例：

7 3 4 5 5 7 6 8 5 4 -> [sort] -> 3 4 4 5 5 5 6 7 7 8 
high numbers: 5 6 7 7 8 
low numbers: 3 4 4 5 5 

Arranged: 
5 3 6 4 7 4 7 5 8 5 = 24 

例：

9 2 5 3 1 -> [sort] -> 1 2 3 5 9 
high numbers: 5 9 
low numbers: 1 2 
left over: 3 

Arranged: 
3 5 1 9 2 = 21  (3 goes at the start, because |3-5| > |3-2|)