白駿12015号:成長が最も長い部分数列2

白駿12015号:成長が最も長い部分数列2

アイデア

前の伯準11053号:成長が最も長い部分数列では、1つの要素の長さを決定するたびに、前のすべての値を探索しなければならない.したがって,時間的複雑度はO(N^2)であり,この方法では入力サイズが1000000の12015回の問題を解決できない.そのため、時間の複雑さを減らす必要があります.
時間の複雑さを減らすのはどこがいいですか?前のすべての要素を参照する必要がありますか?11053回ロック解除すると、dpテーブルはこの値が達成できる最大長を記録したが、今回はこの長さ(index)を昇順で作成する最小値をテーブルに記録した.たとえば、テーブルの2番目のインデックスには最小値が記録され、長さを2にすることができます.

最初に与えられた数列から2番目の値を検索する場合は、長さを2の最小値6に設定できます.ただし、3番目の値を検索した場合は、長さを2の最小値として2とする.同様の方法で、4番目の値を検索すると、長さ3の最小値を4にすることができます.ただし、6番目の値を検索すると、長さを3の最小値3に設定できます.

コード#コード#

N = int(input())
arr = list(map(int, input().split()))
arr.insert(0, 0)
checkLength = [0]


def binarySearch(array, value, low, high):
    if low > high:
        return low
    mid = (low+high) // 2
    if array[mid] > value:
        return binarySearch(array, value, low, mid-1)
    elif array[mid] < value:
        return binarySearch(array, value, mid+1, high)
    else:
        return mid


for i in range(1, N + 1):
    targetIndex = binarySearch(checkLength, arr[i], 0, len(checkLength) - 1)
    if targetIndex >= len(checkLength):
        targetIndex -= 1
    if checkLength[targetIndex] >= arr[i]:
        checkLength[targetIndex] = arr[i]
    else:
        if targetIndex == len(checkLength) - 1:
            checkLength.append(arr[i])


print(len(checkLength) - 1)

おしゃべり

Binary Searchを忘れてGoogleを検索この程度は見ずに実現できるのではないでしょうか.反省しています.