Longest Increasing Subsequence (LIS) uzunluğunu O(n log n) zamanda nasıl bulursunuz?

Klasik DP çözümü O(n²)'dir; O(n log n) çözüm patience sorting fikrine dayanır: tails[k], uzunluğu k+1 olan artan alt dizilerin bitebileceği en küçük değerdir. Her yeni sayı için tails içinde binary search yaparız.

O(n²) DP

dp[i] = i indeksinde biten en uzun artan alt dizinin uzunluğu; dp[i] = 1 + max(dp[j]), j < i ve nums[j] < nums[i].

def lis_n2(nums):
    dp = [1] * len(nums)
    for i in range(len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp, default=0)

O(n log n) çözüm

from bisect import bisect_left

def lis(nums):
    tails = []
    for x in nums:
        i = bisect_left(tails, x)   # x'ten büyük/eşit ilk konum
        if i == len(tails):
            tails.append(x)         # en uzun diziyi uzat
        else:
            tails[i] = x            # daha küçük bir bitiş değeri bulduk
    return len(tails)

print(lis([10, 9, 2, 5, 3, 7, 101, 18]))  # 4  (2, 3, 7, 18)

Neden çalışır?

tails her zaman sıralı kalır. Bir değeri daha küçüğüyle değiştirmek, gelecekte o uzunluktaki diziyi uzatma şansını artırır ve hiçbir zaman mevcut en iyi uzunluğu azaltmaz.

Dikkat

• tails dizisi gerçek LIS'in kendisi değildir, yalnızca uzunluğu doğrudur. Diziyi geri oluşturmak için her elemanın öncülünü (parent indeksi) saklamak gerekir.
• "Non-decreasing" (eşitlere izin) istenirse bisect_right kullanılır.