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 - 查找子阵列之间的最大差异

回答

相关问题