CODEWITHSUNDEEP
rubyarrayssubsequence
Johnson
Johnson

Reputation: 1749

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.

Upvotes: 3

Views: 2175

Answers (1)

Cary Swoveland
Cary Swoveland

Reputation: 110735

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

Upvotes: 3

Related Questions