longest_inc_subseq.rb

# **DP SOLUTION**
def longest_inc_subseq_dp a
  n = a.length
  r = [1]
  s = Array.new(n) {[]}
  s[0] << a[0]

  for i in 1..(n-1)
    res = get_max(a, r, i)
    r[i] = res[0] + 1
    if res[1] == i
      s[i] << a[i]
    else
      s[i] << s[ res[1] ] << a[i]
    end
  end

  return s[ r.index(r.max) ]
end

def get_max a, r, i
  max_len = 0
  max_index = i

  (i-1).downto(0) do |j|
    if a[j] <= a[i] and (r[j] >= max_len)
      max_len = r[j]
      max_index = j
    end
  end

   return [max_len, max_index]
end

# **BRUTE FORCE SOLUTION**
def longest_inc_subseq_brutef a
  return a if a.length == 1

  power_set = a.get_power_set
  max_subseq = []

  power_set.each do |subseq|
    if subseq.is_inc?
      max_subseq = subseq if subseq.length > max_subseq.length
    end
  end
  return max_subseq
end

class Array #adding new methods to Array class

  def is_inc?
    for i in 1..(self.length-1)
      return false if self[i] < self[i-1]
    end
    return true
  end

  def get_power_set
    n = self.length
    ps = [
    for i in 0..(n-1)
      for j in 0..(ps.length-1)
        ps << (ps[j].dup << self[i]) #append ith el to a copy of subsets.
      end
      ps << [self[i]] #add the subset of the ith el itself.
    end
    ps << self #add the whole set
    ps << [] #add the empty set

    return ps
  end

end

  A = [1, 5, 2, 3, 9, 10, 3, 3, 5]
# A = [1, 2, 0, 10]

print longest_inc_subseq_brutef A
print "\n"