Meydan okuma 2
- Algoritmalar kursu
- İleri seviye
- Ders 54/56
- 4 dk
LCS uzunluğunu hesaplayıp yazdırırsın.
Meydan okuma 2: LIS
Bu meydan okumada en uzun artan alt dizi (LIS) problemini çözeceksin. Bir dizideki artan en uzun alt diziyi bulacaksın.
Dizi [10, 9, 2, 5, 3, 7, 101, 18]. LIS uzunluğu 4'tür. DP ile bu sonucu üret.
Uygulama lis_length fonksiyonu
lis_length(arr) yaz. DP ile her i için en uzun artan alt dizi uzunluğunu bul. print(lis_length([10, 9, 2, 5, 3, 7, 101, 18])) ile 4 yazdır.
Başlangıç kodu
def lis_length(arr):
# LIS uzunluğunu DP ile bulÖrnek çözüm
def lis_length(arr):
# LIS uzunluğunu DP ile bul
dp = [1] * len(arr)
for i in range(1, len(arr)):
for j in range(i):
if arr[i] > arr[j]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
print(lis_length([10, 9, 2, 5, 3, 7, 101, 18]))Beklenen çıktı
4
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 LIS koşulu
Soru
if arr[i] ____ arr[j]: dp[i] = max(dp[i], dp[j] + 1)
Cevap
if arr[i] > arr[j]: dp[i] = max(dp[i], dp[j] + 1)Açıklama: > doğru.
2 Meydan okuma 2: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
LIS |
[2,3,7,101] |
uzunluk |
4 |
arr |
8 eleman |
dp |
LIS dizisi |
3 LIS hangi diziyi döner?
- Tüm alt dizileri
- En uzun artan alt dizinin uzunluğunu Doğru cevap
- En kısa alt diziyi
- Sıralı diziyi
Açıklama: LIS en uzun artan alt dizinin uzunluğunu döner.