Debug Longest Increasing Subsequence- Ruby

Question

I'm working on the following problem via Leetcode:

Given an unsorted array of integers, find the length of longest increasing subsequence.

For example, Given [10, 9, 2, 5, 3, 7, 101, 18], The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.

Your algorithm should run in O(n2) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

Trying to implement the first, brute force solution, which essentially is a recursive way to generate every single increasing subsequence then grab the one with the biggest length. After I implement this, I'll use dynamic programming to optimize. I find myself getting confused a bit on the implementation of the brute force-- here's my code:

def length_of_lis(nums)
    1 + max_len(nums, 1, nums.first)
end

def max_len(nums, index, prev_number)
    current_num = nums[index]
    max = 0 
    return 0 if index >= nums.length     
    if current_num > prev_number
        max = [1 + max_len(nums, index + 1, current_num), max].max
    else
        max = [max_len(nums, index + 1, prev_number), max].max
    end 
    max = [1 + max_len(nums, index + 1, current_num), max].max

    max
end

Now I know this is obviously incorrect, but what I was going for was that at each number, a couple things happen. Either 1) it's being passed a function from a previous number, and if this current number is greater than the previous number then continue that function for LIS. 2) Create a new LIS subsequence at the current number.

As you can tell, this creates two identical lines, and I'm not sure how to structure the code such that two separate things happen and the max variable contains the final value. Any ideas of how to adjust this code accordingly?

Answer 1

I've used dynamic programming to obtain an optimal solution.

Code

def construct_sequence(longest, max_i)
  a = []
  loop do
    a << max_i
    max_i = longest[max_i][:next]
    return a if max_i.nil?
  end
end      

def longest_increasing_sequence(arr)
  longest = Array.new(arr.size)
  longest[arr.size-1] = { length: 1, next: nil }
  (arr.size-2).downto(0) do |i|
    best_seq = { length: 1, next: nil }
    (i+1).upto(arr.size-1) do |j| 
      next if arr[j] <= arr[i]
      h = longest[j]      
      best_seq = { length: 1 + h[:length], next: j } if h[:length] >= best_seq[:length]
    end
    longest[i] = best_seq
  end
  max_i = (0..arr.size-1).max_by { |i| longest[i][:length] }
  construct_sequence(longest, max_i)
end

Example

arr = [10, 9, 2, 5, 3, 7, 101, 18]
a = longest_increasing_sequence(arr)
  #=> [2, 3, 5, 6] 
a.each_with_object({}) { |n,h| h[n] = arr[n] }
  #=> {2=>2, 3=>5, 5=>7, 6=>101}

For a second example, I constructed the following 20-element pseudo-random array.

arr = (1..99).to_a.sample(20)
  #=> [80, 75, 13, 12, 85, 16, 41, 89, 93, 56, 74, 18, 37, 24, 27, 63, 47, 83, 25, 44]

longest_increasing_sequence returns an array of indices of arr that constitute a longest increasing sequence.

a = longest_increasing_sequence(arr)
  #=> [2, 5, 11, 13, 14, 15, 17]
a.each_with_object({}) { |n,h| h[n] = arr[n] }
  #=> {2=>13, 5=>16, 11=>18, 13=>24, 14=>27, 15=>63, 17=>83}

Explanation

There is one stage for each element of the array. The state variable is the index of the array where the longest increasing sequence ("LIS") begins. We begin with the last element of the array, which is arr[19] in the example above. If the increasing sequence ("IS") begins there it also ends there. The length of that sequence is 1.

We then move back to stage 18. There are two possibilities: the LS starting at that stage is of length 1, or continues at stage 19 (if the sequence is increasing), in which case it is of length 2.

More generally, if the LIS begins at index i, it may end there or continue, with j being the next index in the LIS, where i+1 <= j <= arr.size-1 and arr[i] < arr[j]. For any such j we have already computed the LIS if the sequence begins at index j, so we know that, from index j, i and j share the same LIS if the next element of the LIS starting at i is j. Therefore, to obtain the LIS starting at i we take the size of the largest LIS for j between i+1 and arr.size-1 for which arr[i] < arr[j] and add 1, unless there are no indices j for which arr[i] < arr[j], in which case the LIS for i ends at i.

The dynamic programming solution rests on the Principle of Optimality, which here is the observation that if index i is a member of an LIS, the collection of indices j, j > i that are also members of that LIS does not depend on the indices j, j < i that are members of that LIS. In other words, the optimal way forward from index i does not depend on how we got there.

To show the details of the calculations I've added some puts statements to longest_increasing_sequence:

def longest_increasing_sequence(arr)
  longest = Array.new(arr.size)
  longest[arr.size-1] = { length: 1, next: nil }
  puts "longest[#{arr.size-1}]=#{longest[arr.size-1]}"
  (arr.size-2).downto(0) do |i|
    best_seq = { length: 1, next: nil }
    puts "i=#{i}"
    puts "  initial best_seq=#{best_seq}"
    (i+1).upto(arr.size-1) do |j| 
      puts "    j=#{j}, arr[#{i}]=#{arr[i]}, arr[#{j}]=#{arr[j]}"   
      next if arr[j] <= arr[i]
      h = longest[j]      
      puts "    h=#{h}"
      puts "    j=#{j} provides new best_seq=#{{length: 1 + h[:length], next: j }}" if
        h[:length] >= best_seq[:length]
      best_seq = { length: 1 + h[:length], next: j } if h[:length] >= best_seq[:length]
    end
    longest[i] = best_seq
  end
  longest.each_index { |i| puts "i=#{i}: #{longest[i]}" }
  max_i = (0..arr.size-1).max_by { |i| longest[i][:length] }
  construct_sequence(longest, max_i)
end

arr = [60, 29, 56, 46, 37, 57, 28, 44]
longest_increasing_sequence(arr)

longest[7]={:length=>1, :next=>nil}
i=6
  initial best_seq={:length=>1, :next=>nil}
    j=7, arr[6]=28, arr[7]=44
    h={:length=>1, :next=>nil}
    j=7 provides new best_seq={:length=>2, :next=>7}
i=5
  initial best_seq={:length=>1, :next=>nil}
    j=6, arr[5]=57, arr[6]=28
    j=7, arr[5]=57, arr[7]=44

i=4
  initial best_seq={:length=>1, :next=>nil}
    j=5, arr[4]=37, arr[5]=57
    h={:length=>1, :next=>nil}
    j=5 provides new best_seq={:length=>2, :next=>5}
    j=6, arr[4]=37, arr[6]=28
    j=7, arr[4]=37, arr[7]=44
    h={:length=>1, :next=>nil}
i=3
  initial best_seq={:length=>1, :next=>nil}
    j=4, arr[3]=46, arr[4]=37
    j=5, arr[3]=46, arr[5]=57
    h={:length=>1, :next=>nil}
    j=5 provides new best_seq={:length=>2, :next=>5}
    j=6, arr[3]=46, arr[6]=28
    j=7, arr[3]=46, arr[7]=44
i=2
  initial best_seq={:length=>1, :next=>nil}
    j=3, arr[2]=56, arr[3]=46
    j=4, arr[2]=56, arr[4]=37
    j=5, arr[2]=56, arr[5]=57
    h={:length=>1, :next=>nil}
    j=5 provides new best_seq={:length=>2, :next=>5}
    j=6, arr[2]=56, arr[6]=28
    j=7, arr[2]=56, arr[7]=44

i=1
  initial best_seq={:length=>1, :next=>nil}
    j=2, arr[1]=29, arr[2]=56
    h={:length=>2, :next=>5}
    j=2 provides new best_seq={:length=>3, :next=>2}
    j=3, arr[1]=29, arr[3]=46
    h={:length=>2, :next=>5}
    j=4, arr[1]=29, arr[4]=37
    h={:length=>2, :next=>5}
    j=5, arr[1]=29, arr[5]=57
    h={:length=>1, :next=>nil}
    j=6, arr[1]=29, arr[6]=28
    j=7, arr[1]=29, arr[7]=44
    h={:length=>1, :next=>nil}
i=0
  initial best_seq={:length=>1, :next=>nil}
    j=1, arr[0]=60, arr[1]=29
    j=2, arr[0]=60, arr[2]=56
    j=3, arr[0]=60, arr[3]=46
    j=4, arr[0]=60, arr[4]=37
    j=5, arr[0]=60, arr[5]=57
    j=6, arr[0]=60, arr[6]=28
    j=7, arr[0]=60, arr[7]=44
i=0: {:length=>1, :next=>nil}
i=1: {:length=>3, :next=>2}
i=2: {:length=>2, :next=>5}
i=3: {:length=>2, :next=>5}
i=4: {:length=>2, :next=>5}
i=5: {:length=>1, :next=>nil}
i=6: {:length=>2, :next=>7}
i=7: {:length=>1, :next=>nil}
  #=> [1, 2, 5]