title: Finding the longest growing sequence in an array of arrays with Ruby
body: <p>I have an array of arrays which contains integers. For example:</p>
  
  <pre><code>arr=[[109, 160, 184, 229],
  [45, 67, 158, 175, 201, 250, 273],
  [33, 86, 89, 182, 245, 251, 254, 272],
  [35, 76, 93, 143, 222, 267],
  [189, 242],
  [19],
  [41, 58, 135, 256],
  [59],
  [60, 138, 183, 203, 246],
  [45, 67, 158, 175, 197, 201, 250, 273],
  [55, 57, 101, 103, 193, 212, 231, 257],
  [18, 23, 51, 75, 106, 139, 179, 247],
  [31, 72, 92, 99, 148, 230],
  [128, 142, 151, 164, 170, 173, 196, 226],
  [15],
  [4],
  [41, 113, 135, 256],
  [33, 251]]
  </code></pre>
  
  <p>Look at the whole example array here <a href="http://pastebin.com/exzi8Mnq" rel="nofollow">http://pastebin.com/exzi8Mnq</a></p>
  
  <p>Every nested array is sorted, and contains uniqe elements, no duplicates, they contains at least one element, at most there are no limit (usually maximum 10-15 elements) and 200-2000 nested arrays in total.</p>
  
  <p>I would like to find the longest sequence of the integers across the arrays which elements monotonously grows, without equality. For example one element from the first array, the second is from the second array, etc. Every nested array should provide only one element or zero. Maybe the first element doesn't origin from the first array, but the second, or third, or more, to ensure finally the longest growing sequence. In top of that some of the nested arrays could be skipped, I mean they don't provide any element to the result sequence. </p>
  
  <p>You can imagine a looong number in a numeral system which radix is equal to the size of the largest nested array and the digits may refer to the the nested arrays, so we can count all the possible sequences. For example 0123 would represent that sequence that first element is chosen from the second array,  and its index is 0 (1-1). Second element is chosen from the 3rd array, and its index is 2 (3-1) First digit 0 represents that no integer is chosen from the first array. The allowed maximal value of a digit is limited by the size of the given nested array.</p>
  
  <p>Example output: [45, 86, 93, 189]
  First element was chosen from the second array, second from the third array, etc. However this is obviously not the longest sequence which can be extracted.</p>
  
  <p>I think some kind of backtracking or creating the product of all array to an enumerator and examine the result.</p>
  
  <p>I need this method for my subtitle timing program.</p>