algorithm - 最長増加部分列 2d

Question

m 個の整数のn 個のソートされた配列を固定順序で持っています。サブシーケンスのすべての要素が正確に 1 つの配列に属するように、最も長く増加するサブシーケンスを見つける必要があります。O (n ² )よりもうまくできるでしょうか?

Answer 1

@svs に沿って、これは O(m * n) 未満で達成することはできません。ただし、実際には、配列内でより長いサブシーケンスを見つけることができないことがわかったら、配列の反復を終了することで平均最悪時間を短縮できます。

些細なループ:

maxList = []
for arr in arrays:
    last = arr[0] - 1
    tempList = []
    for element in arr:
        if element > last:
            tempList.append(element)
            if len(tempList) > len(maxList):
                    maxList = tempList

        else:
            tempList = [element]
        last = element

return (maxList, iters)

冗長なループ反復を無視して:

maxList = []
for arr in arrays:
    if len(maxList) == len(arr):
        break

    last = arr[0] - 1
    tempList = []
    for (index, element) in enumerate(arr):
        if element > last:
            tempList.append(element)
            if len(tempList) > len(maxList):
                    maxList = tempList[:]
        else:
            tempList = [element]

        # if continuing looking down the array could not result in a longer
        # increasing sequence
        if (len(tempList) + (len(arr) - (index + 1)) <= len(maxList)):
            break

        last = element

return (maxList, iters)