Johnson - 3 months ago 15
Ruby Question

# Ruby - Finding the Maximum Difference among subarrays

I came across a question from a coding challenge site that deals with subsequences.

Given an array of integer elements, a subsequence of this array is a set of consecutive elements from the array (i.e: given the array v: [7, 8, -3, 5, -1], a subsequence of v is 8, -3, 5)

Your task is to write a function that finds a left and a right subsequence of the array that satisfy the following conditions:

1. Two subsequences must be unique (they donâ€™t have shared elements)

2. The difference between the sum of the elements in the right subsequence and the sum of the elements in the left subsequence is maximum

3. Print the difference to the standard output (stdout)

The function receives array, which is an array of integers.

Data constraints:

1. the array has at least 2 and at most 1,000,000 numbers

2. all the elements in the array are integer numbers in the following range: [-1000, 1000]

Example

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

In the above example, the left subsequence is [-5, 1, -2] and the right subsequence is [8,-2,3]

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

Here's what I've tried

``````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
``````

but it looks like that doesn't work.

What I have done is condition on partitions of the array, such that both the "left" and "right" arrays each contain at least one element. For each partition, I then find the sequence in the left array whose sum is minimum, and the sequence in the right array whose sum is maximum, and maximize the difference over all partitions.

Code

``````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
``````

Example

``````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
``````