Отладка самой длинной возрастающей подпоследовательности - Ruby

Question

Я работаю над следующей проблемой через Leetcode:

Учитывая несортированный массив целых чисел, найдите длину самой длинной увеличивающейся подпоследовательности.

Например, учитывая [10, 9, 2, 5, 3, 7, 101, 18], самая длинная возрастающая подпоследовательность равна [2, 3, 7, 101], поэтому длина равна 4. Обратите внимание, что может быть больше, чем одна комбинация LIS, вам нужно только вернуть длину.

Ваш алгоритм должен работать в сложности O(n2).

Продолжение: Не могли бы вы улучшить его до O(n log n) сложности времени?

Попытка реализовать первое решение методом грубой силы, которое, по сути, является рекурсивным способом генерирования каждой увеличивающейся подпоследовательности, затем захватывает самую большую подпоследовательность. После этого я буду использовать динамическое программирование для оптимизации. Я немного запутался в реализации грубой силы - вот мой код:

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

Теперь я знаю, что это, очевидно, неправильно, но я рассчитывал на то, что на каждом номере происходит пара вещей. Либо 1) ему передается функция от предыдущего номера, и если этот текущий номер больше предыдущего номера, то продолжите эту функцию для LIS. 2) Создайте новую подпоследовательность LIS под текущим номером.

Как вы можете сказать, это создает две одинаковые строки, и я не уверен, как структурировать код так, чтобы две отдельные вещи происходили, а переменная max содержала окончательное значение. Любые идеи о том, как настроить этот код соответственно?

Answer 1

Я использовал динамическое программирование, чтобы получить оптимальное решение.

Код

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

пример

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}

Для второго примера я построил следующий 20-элементный псевдослучайный массив.

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 возвращает массив индексов arr которые составляют самую длинную возрастающую последовательность.

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}

объяснение

Существует один этап для каждого элемента массива. Переменная состояния - это индекс массива, где начинается самая длинная возрастающая последовательность ("LIS"). Мы начинаем с последнего элемента массива, который arr[19] в приведенном выше примере. Если там начинается последовательность возрастания ("IS"), она также заканчивается там. Длина этой последовательности 1,

Затем мы возвращаемся к этапу 18. Есть две возможности: LS, начинающийся на этом этапе, имеет длину 1 или продолжается на этапе 19 (если последовательность увеличивается), и в этом случае она имеет длину 2,

В целом, если LIS начинается с индекса i, это может закончиться или продолжиться, с j являясь следующим индексом в ЛИС, где i+1 <= j <= arr.size-1 а также arr[i] < arr[j], Для любого такого j мы уже вычислили LIS, если последовательность начинается с индекса j Итак, мы знаем, что из индекса j, i а также j использовать одну и ту же LIS, если следующий элемент LIS начинается с i является j, Поэтому, чтобы получить LIS, начиная с i мы берем размер самой большой LIS для j между i+1 а также arr.size-1 для которого arr[i] < arr[j] и добавить 1, если нет индексов j для которого arr[i] < arr[j] в этом случае ЛИС для i заканчивается в i,

Решение для динамического программирования основывается на принципе оптимальности, который здесь заключается в том, что если индекс i является членом ЛИС, коллекция индексов j, j > i которые также являются членами этой LIS не зависит от индексов j, j < i которые являются членами этой ЛИС. Другими словами, оптимальный путь вперед от индекса i не зависит от того, как мы туда попали.

Чтобы показать детали расчетов, я добавил несколько операторов put 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]