9. Sınıf Tüketme Yaklaşımı ve Kadane Algoritmasını Karşılaştırma Nedir? Test 1

Kadane Algoritması ile ilgili aşağıdaki ifadelerden hangisi doğrudur?

A) Tüm alt dizileri tek tek kontrol eder
B) Zaman karmaşıklığı O(n²)'dir
C) Dinamik programlama prensibine dayanır
D) Sadece pozitif sayılar içeren dizilerde çalışır

Kadane Algoritması, bir dizideki bitişik alt dizilerin (contiguous subarray) maksimum toplamını bulan etkili bir algoritmadır. Şimdi seçenekleri adım adım inceleyelim:

• A) Tüm alt dizileri tek tek kontrol eder
  Bu ifade yanlıştır. Eğer tüm alt diziler tek tek kontrol edilseydi, bu bir "kaba kuvvet" (brute-force) yaklaşımı olurdu ve zaman karmaşıklığı $O(n^2)$ veya $O(n^3)$ olurdu. Kadane Algoritması, bu kadar çok kontrol yapmadan çok daha verimli bir şekilde çalışır.
• B) Zaman karmaşıklığı O(n²)'dir
  Bu ifade yanlıştır. Kadane Algoritması, diziyi sadece bir kez tarayarak çözüm üretir. Bu nedenle, zaman karmaşıklığı $O(n)$'dir, yani dizi boyutuyla doğrusal olarak artar. Bu, onu oldukça hızlı ve verimli bir algoritma yapar.
• C) Dinamik programlama prensibine dayanır
  Bu ifade doğrudur. Kadane Algoritması, dinamik programlamanın temel prensiplerinden olan "optimal alt yapı" (optimal substructure) ve "çakışan alt problemler" (overlapping subproblems) özelliklerini kullanır. Algoritma, her adımda o ana kadar görülen en büyük toplamı (genel maksimum) ve mevcut elemanla biten en büyük toplamı (yerel maksimum) takip eder. Mevcut elemanla biten en büyük toplam, ya sadece mevcut elemanın kendisidir ya da mevcut eleman ile bir önceki elemanla biten en büyük toplamın birleşimidir. Bu, bir önceki adımın çözümünü kullanarak mevcut adımın çözümünü bulma mantığıdır ki bu da dinamik programlamanın tipik bir özelliğidir.
• D) Sadece pozitif sayılar içeren dizilerde çalışır
  Bu ifade yanlıştır. Kadane Algoritması, negatif sayılar içeren dizilerde de doğru bir şekilde çalışır. Hatta, algoritmanın en önemli özelliklerinden biri, negatif sayıların varlığında bile maksimum toplamı bulabilmesidir. Eğer tüm sayılar negatifse, algoritma en büyük (sıfıra en yakın) negatif sayıyı döndürür. Örneğin, $[-2, -3, -1]$ dizisi için maksimum toplam $-1$'dir ve Kadane algoritması bunu doğru bir şekilde bulur.

Cevap C seçeneğidir.