白駿12015号:成長が最も長い部分数列2
7369 ワード
白駿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に設定できます.
Binary Searchを忘れてGoogleを検索この程度は見ずに実現できるのではないでしょうか.反省しています.
アイデア
前の伯準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を検索この程度は見ずに実現できるのではないでしょうか.反省しています.
Reference
この問題について(白駿12015号:成長が最も長い部分数列2), 我々は、より多くの情報をここで見つけました https://velog.io/@ks1ksi/백준-12015번-가장-긴-증가하는-부분-수열-2テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol