Maksimum Alt Dizi Toplamı: Kadane Algoritması
Sorun bildirimi
Alt diziler, yalnızca bitişik öğeler içeren başka bir dizinin içindeki dizilerdir.
Bir tamsayı dizisi verildiğinde, görev, boş olmayan tüm alt dizilerin mümkün olan maksimum alt dizi toplamını bulmaktır.
Örnek vermek:
Girdi: [-3, -4, 5, -1, 2, -4, 6, -1]
Çıktı: 8
Açıklama: Alt dizi [5, -1, 2, -4, 6] ile maksimum toplam bitişik alt
dizidir. toplam 8.
Girdi: [-2, 3, -1, 2]
Çıktı: 4
Açıklama: Alt dizi [3, -1, 2] toplamı 4 olan maksimum toplam bitişik
alt dizidir.
Yaklaşımları izleyerek sorunu çözeceğiz -
- Basit yaklaşım
- Verimli Yaklaşım: Kadane Algoritması
Basit Yaklaşım:
Bu sorunu çözmenin basit yaklaşımı, iki for döngüsü çalıştırmak ve her alt dizi için mümkün olan maksimum toplam olup olmadığını kontrol etmektir. Sorunu çözmek için aşağıdaki adımları izleyin.
- i için 0'dan n – 1'e kadar bir döngü çalıştırın; burada n, dizinin boyutudur.
- Şimdi, j için i'den n – 1'e kadar yuvalanmış bir döngü çalıştıracağız ve j dizinindeki öğenin değerini bir currentMax değişkenine ekleyeceğiz.
- Son olarak, her alt dizi için, currentMax'in tüm bitişik alt dizilerin maksimum toplamı olup olmadığını kontrol edeceğiz.
C uygulaması
C++ uygulaması
Java uygulaması
Python uygulaması
Zaman karmaşıklığı: O(N^2), Burada N, dizinin boyutudur.
Uzay karmaşıklığı: O(1)
Verimli Yaklaşım: Kadane Algoritması
Kadane Algoritması , yinelemeli bir dinamik programlama algoritmasıdır. Bir önceki konumda biten maksimum toplam alt dizisini kullanarak belirli bir konumda biten maksimum toplam alt diziyi hesaplar. Sorunu çözmek için aşağıdaki adımları izleyin.
- Burada biten maksimum toplamı depolayan iki değişkenli currSum ve o ana kadar maksimum toplamı depolayan maxSum tanımlayın.
- currSum'u 0 ile ve maxSum'u INT_MIN ile başlatın.
-
Şimdi, diziyi yineleyin ve mevcut öğenin değerini currSum'a
ekleyin ve kontrol edin.
- CurrSum maxSum'dan büyükse, maxSum güncellemesi currSum'a eşittir.
- currSum sıfırdan küçükse, currSum'u sıfıra eşit yapın.
- Son olarak, maxSum değerini yazdırın.
Yukarıdaki yaklaşımın kuru çalışması
C Verimli yaklaşımın uygulanması
Verimli yaklaşımın C++ uygulaması
Verimli yaklaşımın Java uygulaması
Verimli yaklaşımın Python uygulaması
Zaman karmaşıklığı: O(N), Burada N, dizinin boyutudur.
Uzay karmaşıklığı: O(1)
Sıkça Sorulan Sorular
S. Kadane'nin algoritması Dinamik Programlama mı?
C. Evet, yinelemeli bir dinamik programlama algoritmasıdır.
S. Dizinin tüm öğeleri negatifse, maksimum alt dizi toplamı ne
olmalıdır?
A. Boş alt diziyi düşünüp düşünmediğimize bağlı. Boş bir alt diziyi düşünürsek, çıktı 0 olmalıdır, çıktı dizinin
maksimum elemanı olmalıdır (0'a en yakın eleman).
S. Kadane'nin algoritmasının zaman karmaşıklığı nedir?
A. Kadane'nin algoritmasının zaman karmaşıklığı O(N)'dir, burada
N, dizinin boyutudur.
