Ruby - finding maximum difference between subarrays
I stumbled upon a question from an encoding request site that is about subsequence.
Given an array of integer elements, a subsequence of this array is a set of sequential elements from the array (ie a given array v: [7, 8, -3, 5, -1], subsequence v 8, -3, 5)
Your task is to write a function that finds the left and right subsequences of an array that satisfy the following conditions:
-
Two subsequences must be unique (they have no common elements)
-
The difference between the sum of elements in the right subsequence and the sum of elements in the left subsequence is maximal
-
Print the difference with standard output (stdout)
The function gets an array , which is an array of integers.
Data limitations:
-
an array has at least 2 and at most 1,000,000 numbers
-
all elements of the array are integers 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 is what I have 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 it won't work.
source to share
What I have done is conditional on the partitions of the array so that each of the "left" and "right" arrays contains at least one element. For each section, I then find the sequence in the left array that has the minimum sum, and the sequence in the right array that has the maximum sum, and maximizes the difference across all sections.
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
source to share