3

我在一个处理子序列的编码挑战网站上遇到了一个问题。

给定一个整数元素数组，这个数组的子序列是数组中的一组连续元素（即：给定数组v：[7, 8, -3, 5, -1]，v的子序列是8， -3, 5)

你的任务是编写一个函数，找到满足以下条件的数组的左子序列和右子序列：

  1. 两个子序列必须是唯一的（它们没有共享元素）

  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

我所做的是对数组分区的条件，使得“左”和“右”数组每个都包含至少一个元素。对于每个分区，然后我找到左侧数组中总和最小的序列，以及右侧数组中总和最大的序列，并最大化所有分区的差异。

代码

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 回答