3

サブシーケンスを扱うコーディング チャレンジ サイトからの質問に出会いました。

整数要素の配列が与えられると、この配列のサブシーケンスは、配列からの連続した要素のセットになります (つまり、配列 v: [7, 8, -3, 5, -1] が与えられると、v のサブシーケンスは 8、 -3, 5)

あなたの仕事は、次の条件を満たす配列の左と右のサブシーケンスを見つける関数を書くことです:

  1. 2 つのサブシーケンスは一意である必要があります (共有要素はありません)。

  2. 右側の部分列の要素の合計と左側の部分列の要素の合計の差は最大です

  3. 差分を標準出力 (stdout) に出力します。

この関数は、整数の配列である array を受け取ります。

データの制約:

  1. 配列には、少なくとも 2 つ、最大で 1,000,000 の数字があります

  2. 配列内のすべての要素は、次の範囲の整数です: [-1000, 1000]

例

Input: 3, -5, 1, -2, 8, -2, 3, -2, 1
Output: 15

上記の例では、左側のサブシーケンスは [-5, 1, -2] であり、右側のサブシーケンスは [8,-2,3] です。

(8 + -2 + 3) - (-5 + 1 + -2) = 9 - -6 = 15

これが私が試したことです

def maximum_difference(array)
  sequences = array.each_cons(3).to_a
  pairs = sequences.each_cons(2).to_a
  pairs.select{|pair|pair[0]+pair[1].length != pair[0] + pair[1].uniq.length}
  pairs.map{|values|values.reduce(:+)}.sort{|max, min| max - min}
end

しかし、それはうまくいかないようです。

4

1 に答える 1

3

私が行ったことは、「左」配列と「右」配列の両方に少なくとも1つの要素が含まれるように、配列のパーティションを条件付けすることです。次に、パーティションごとに、左の配列で合計が最小になるシーケンスと、右の配列で合計が最大になるシーケンスを見つけ、すべてのパーティションで差を最大化します。

コード

def largest_diff(arr)
  (arr.size-2).times.map { |n|
    [min_sub(arr[0..n]), max_sub(arr[n+1..-1])] }.max_by { |l,r|
    r.reduce(:+) - l.reduce(:+) }
end

private

def max_sub(arr)
  max_min_sub(arr, :max_by)
end

def min_sub(arr)
  max_min_sub(arr, :min_by)
end

def max_min_sub(arr, max_min_by)
  (1..arr.size).map { |i| arr.each_cons(i).send(max_min_by) { |b|
    b.reduce(:+) } }.send(max_min_by) { |b| b.reduce(:+) }
end

例

arr = [3, -5, 1, -2, 8, -2, 3, -2, 1]

seq = (arr.size-2).times.map { |n|
        [min_sub(arr[0..n]), max_sub(arr[n+1..-1])] }.max_by { |l,r|
        r.reduce(:+) - l.reduce(:+) }
  #=> [[-5, 1, -2], [8, -2, 3]]

seq.last.reduce(:+) - seq.first.reduce(:+)
  #=> 15
于 2014-09-22T22:29:42.723 に答える