Ruby - 查找子陣列之間的最大差異

我遇到了一個來自編碼挑戰網站的問題，它處理子序列。給定一個整數元素的數組，這個數組的子序列是數組中的一組連續元素（即：給定數組v：[7,8，-3,5，-1]，其子序列爲v是8，-3，5）Ruby - 查找子陣列之間的最大差異

你的任務是編寫發現左和滿足以下條件的陣列的右子序列的函數：

兩個子序列必須是唯一的（他們沒有共享元素）
區別烯在右子序列和在左側的子序列中的元素的總和的元素的總和爲最大
打印的差到標準輸出（stdout）

功能接收陣列，這是一個整數數組。

數據約束：

所述陣列具有至少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

但它看起來不起作用。

來源

2014-09-22 Johnson

在問題指出序列必須是唯一的三位數字的長無。實際上，樣本輸入可能只有兩位數字，所以序列可以是一位數字。你不能通過硬編碼每組3個項目的對來解決這個問題。 – meagar 2014-09-22 20:53:17

我們是最大化'sum（right） - sum（left）'還是'abs（sum（right） - sum（left））'？ – hobbs 2014-09-22 22:37:50

我所做的是數組的分區條件，使「左」和「右」數組都包含至少一個元素。然後，對於每個分區，我會在總數最小的左側數組中找到序列，並且在右側數組中它們的總和最大的序列，並最大化所有分區之間的差異。

代碼

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-22 22:29:42

Ruby - 查找子陣列之間的最大差異

回答

相關問題