Нахождение непрерывной числовой последовательности

Question

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

Пример ([] - представляет массив (как в javascript)):

[
    [1, 5, 6],
    [7],
    [22, 34],
    [500, 550],
    [60, 1],
    [90, 100],
    [243],
    [250, 110],
    [150],
    [155],
    [160]
]

Правильный вывод будет: [1, 7, 22, 60, 90, 110, 150, 155, 160]

Подробный вывод:

1,   -- index  1 all 1, 5 and 6 would match here, pick the smallest
7,   -- index  2
22,  -- index  3
     -- index  4 skipped, the sequence would end here or wouldn't be the longest possible
60,  -- index  5 picked 60, because 1 wouldn't continue in the sequence
90,  -- index  6
     -- index  7 skipped, the sequence would end here or wouldn't be the longest possible
110, -- index  8
150, -- index  9
155, -- index 10
160  -- index 11

Answer 1

Возможный подход заключается в использовании динамического программирования с использованием в качестве параметров последнего значения и индекса первого подмассива для рассмотрения.

Это решение на Python, основанное на рекурсии с памяткой

data = [[1, 5, 6],
        [7],
        [22, 34],
        [500, 550],
        [60, 1],
        [90, 100],
        [243],
        [250, 110],
        [150],
        [155],
        [160]]

def longest(x0, i, _cache=dict()):
    if i == len(data):
        return []
    try:
        return _cache[x0, i]
    except KeyError:
        best = longest(x0, i+1)
        for x in data[i]:
            if x >= x0:
                L = [x] + longest(x, i+1)
                if len(L) > len(best):
                    best = L
        _cache[x0, i] = best
        return best

print longest(0, 0)