Johnson - 1 year ago 62

Ruby Question

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:

- Two subsequences must be unique (they donâ€™t have shared elements)
- The difference between the sum of the elements in the right subsequence and the sum of the elements in the left subsequence is maximum
- Print the difference to the standard output (stdout)

The function receives

Data constraints:

- the array has at least 2 and at most 1,000,000 numbers
- 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.

Answer Source

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