百準14003成長最長の部分数列5

質問する

コード#コード#

n = int(input())

arr = list(map(int, input().split()))

dp = [arr[0]]
index = [1]
for i in range(1, n):
    if dp[-1] < arr[i]:
        dp.append(arr[i])
        index.append(len(dp))
    else:
        low = 0
        high = len(dp)-1
        idx = 0
        while low <= high:
            mid = (low+high)//2
            if dp[mid] >= arr[i]:
                idx = mid
                high = mid-1
            elif dp[mid] < arr[i]:
                low = mid+1
        else:
            dp[idx] = arr[i]
            index.append(idx+1)
temp = len(dp)
print(temp)
result = []
for i in range(len(index)-1, -1, -1):
    if temp == index[i]:
        result.append(arr[i])
        temp -= 1

print(*list(reversed(result)))

に答える