Bir dizi içerisinde en uzun artan altdiziyi bulmayı amaçlayan bir problemdir. Örneğin
Input:
{10, 22, 9, 33, 21, 50, 41, 60, 80}
Output:
6{10, 22, 33, 50, 60, 80}
LCS algoritmasına benzer bir yol izleyeceğiz. Kod anlaşılır durumda, çözüm aşağıdadır.
def lis(arr):
lis = [1] * len(arr)
for i in range(1, len(arr)):
for j in range(i):
if arr[i] > arr[j] and lis[i] < lis[j] + 1:
lis[i] = lis[j] + 1
return max(lis)
if __name__ == '__main__':
arr = [10, 22, 9, 33, 21, 50, 41, 60]
print(lis(arr))
Yukarıdaki algoritmanın zaman karmaşıklığı O(n^2)'dir. Algoritma farklı bir yaklaşım ile O(nlogn) karmaşıklık ile çözülebilir. İncelemek için : link
Comments
comments powered by Disqus