絶対差を最大にする

Question

それぞれがある値を持つコインの配列を与えられます。配列のサイズはNです。最初と最後のコイン以外のコインの値を変更することができます。 i番目のコインの値を（i-1）番目と（i + 1）番目のコインの合計額の半分に変更することができますが、2つの条件を満たす必要があります。

（1）コイン番目（I-1）番目と（i + 1）の両方の値が偶数であるべきであり、j番目の硬貨の値がi番目の硬貨の値の後に変更された場合

（2）次に、jが大きくなければなりませんあなたの仕事は、配列のコインの前半と配列のコインの後半の値の合計の絶対差を最大にすることです。配列のサイズが奇数の場合、中間要素を無視します。

誰でも私に答えを見つけるためにアルゴを提案できますか？

タスクは、最大絶対差分を見つけることです。

私のalgo：1.左半分>右半分は左半分を最大化する操作を与え、左半分を最小化しますが、正解は得られません。

PS：1週間前にインタビューを受けました。そこに私はアプローチを理解できないと尋ねられました。

Answer 1

私はブルートフォースよりも洗練されたアルゴリズムを考えることができませんでした。可能性のあるものすべてを試して、最良の結果を返すだけです。私は再帰的なアプローチをお勧めします。入力リストとインデックスをパラメータとして持つ再帰関数を記述します。この関数は、そのインデックスにある数値を変更しようとし、最良の結果を返します。最後に、最良の結果を印刷する必要があります。それは複雑に思えますが、実際には簡単です。このコードを見てみましょう：

[10, 4, 22, 43, 64]

の最終的なリストについては

93 

を印刷します。しかし、この方法は非効率的であり、大きな入力に対して動作しないことを心に留めておく

def func(input_list, index): 
    # if we have reached the end of the list 
    # we compute the result and return it 
    L = input_list[:] 
    if index == len(L): 
    # return absolute difference of the two halves 
     return abs (sum(L[:len(L)/2]) - sum(L[int(len(L)/2.0 + 1):])) 

    #result of not changing this item 
    no_change = func(L, index+1) 

    #check if it is possible to change this item 
    change = 0 
    if index-1 >= 0 and index+1 < len(L) and L[index-1]%2==0 and L[index+1]%2==0: 
     #result of changing this item if possible 
     L[index] = (L[index-1] + L[index+1])/2 
     change = func(L, index+1) 

    #return the maximum result of changing and not changing 
    best = max(no_change, change) 
    return best 


L = [10, 4, 22, 8, 64] 
print func(L, 0) 

。

Answer 2

ブルートフォースアルゴリズムではいくつかの最適化が可能です。

右に続くすべてのデータから計算された可能な合計を各インデックスに格納するアルゴリズムを作成できます。その情報は、再帰のバックトラッキング中に埋められます。

例：簡略化するために、前半の合計を最大化し、後半の合計を最小化することのみを検討します。

[4, 1, 8, 2, 4, 1, 4] 

アルゴリズムは、配列の最後の要素に向けて深さ優先行き、その後、唯一の右に以下のものを考慮すると、そこに最高の合計を格納します。右には何もないので、合計は4です。しかし、最小化したいときは、符号を切り替えます。そこで、次のようなものを保存します。

[4, 1, 8, 2, 4, 1, 4] 
        -4 

次に戻ってきます。現時点では2つの可能性があります。1をそのまま残すか、または周囲の値の平均を使用します（つまり、4）：

[4, 1, 8, 2, 4, 1, 4] 
        -4 
       -5 
[4, 1, 8, 2, 4, 4, 4] 
        -4 
       -8 

両方の値-5及び-8値1について、我々は-5を見つけることができるように、ハッシュに保存され、値4のために、我々は-8を見つけることができます。

アルゴリズムの特定のポイントで、（1ではなく）2番目の配列要素で値6を試してから、再度再帰します。 1つ前の要素に到達すると、可能な値は再び1または4になります（他に何も変更されていない場合）ので、深く反復する必要はありません。そのインデックスで維持しているハッシュからの合計です。

このシステムでは、大規模な配列で多くの節約効果を得ることができます。実際に必要なときにアルゴリズムが再帰的に深くなるようにします。明らかに、それはスペースの点でコストがかかります。

次に、アルゴリズム全体をもう一度実行することができますが、その後、符号を入れ替えることができます。これらの2つの結果のうち、最良の解が取られ、絶対値が最大になります。

おそらく変更された要素の値を関数の引数として渡すことによって、複数の配列を作成することを避けることができ、入力配列で作業することができます。一方、各インデックスで作成されたハッシュにはいくらかのスペースが必要です。

function getMaxSum(a) { 
 
    // Index of the element in the middle. If integer, 
 
    // the element at this index will not play a role in any sum: 
 
    var mid = (a.length-1)/2; 
 
    // Two results, one that maximises the left sum and minimises the right sum 
 
    // The other minimises the left and maximises the right: 
 
    var result, result2, b; 
 

 
    function recurse(prevVal, index, sign, hash = []) { 
 
     var val, nextVal, sum, result, avg; 
 
     
 
     val = a[index]; 
 
     if (index >= a.length-1) { 
 
      // At the last element there are no choices left: 
 
      return { sum: -sign*(prevVal+val), nextVal: val, hash: [] }; 
 
     } 
 
     if (!hash[index]) hash[index] = []; 
 
     nextVal = a[index+1]; 
 
     result = { sum: -Infinity, nextVal: 0, hash: hash[index] }; 
 
     // Loop through the 2 possibilities (in general): take value as is, or 
 
     // take the average of previous and next value: 
 
     while (true) { 
 
      // If the result from this position onward is not know, calculate 
 
      // it via a recursive call: 
 
      if (!hash[index][val]) hash[index][val] = recurse(val, index+1, sign, hash); 
 
      // Add the previous value to the best sum at this point, using the appropriate sign, 
 
      // and store the result in a hash table, for future reference: 
 
      sum = hash[index][val].sum + (index-1 > mid ? -1 : index-1 < mid ? 1 : 0) * sign * prevVal; 
 
      if (sum > result.sum) { 
 
       result.sum = sum; 
 
       result.nextVal = val; 
 
      } 
 
      if (prevVal % 2 || nextVal % 2 || (avg = (prevVal + nextVal)/2) === val) break; 
 
      val = avg; 
 
     } 
 
     return result; 
 
    } 
 

 
    // Calculate both results 
 
    result = recurse(a[0], 1, 1, []); 
 
    result2 = recurse(a[0], 1, -1, []); 
 
    // Pick the best one. 
 
    if (Math.abs(result2.sum) > Math.abs(result.sum)) result = result2; 
 

 
    // Rebuild the array corresponding to the best result: 
 
    b = [a[0]]; 
 
    while (result) { 
 
     b.push(result.nextVal); 
 
     result = result.hash[result.nextVal]; 
 
    } 
 
    return b; 
 
} 
 

 
// Sample data 
 
var a = [4, 1, 8, 2, 4, 1, 4]; 
 
console.log(' input: ' + a); 
 
// Apply algorithm 
 
var b = getMaxSum(a, 1); 
 
// Print result 
 
console.log('result: ' + b);