Maksimum Alt Dizi Problemi, Maksimum Dilim Problemi ile aynıdır. Bu öğretici, C++'da kodlamayla ilgili sorunu tartışıyor. Soru şudur: Bir dizideki olası herhangi bir ardışık sayı dizisinin maksimum toplamı nedir? Bu, tüm dizi anlamına gelebilir. Bu problem ve herhangi bir dilde çözümü, Maksimum Alt Dizi Problemi olarak adlandırılır. Dizi olası negatif sayılara sahip olabilir.
Çözüm verimli olmalıdır. En hızlı zaman karmaşıklığına sahip olması gerekir. Şu an itibariyle çözüm için en hızlı algoritma bilim camiasında Kadane Algoritması olarak biliniyor. Bu makale Kadane'nin C++ ile algoritmasını açıklamaktadır.
Veri Örnekleri
Aşağıdaki vektörü (diziyi) göz önünde bulundurun:
vektör < int > bir = { 5 , - 7 , 3 , 5 , - iki , 4 , - 1 } ;
Maksimum toplamı olan dilim (alt dizi), toplam 10 veren {3, 5, -2, 4} dizisidir. Başka hiçbir olası dizi, hatta tüm dizi bile, en fazla toplamını vermez. 10 değeri. Tüm dizi, maksimum toplam olmayan 7 toplamını verir.
Aşağıdaki vektörü düşünün:
vektör < int > B = { - iki , 1 , - 3 , 4 , - 1 , iki , 1 , - 5 , 4 } ;
Maksimum toplamı olan dilim (alt dizi), 6 toplamı veren {4, -1, 2, 1} dizisidir. Maksimum toplam için alt dizi içinde negatif sayılar olabileceğini unutmayın.
Aşağıdaki vektörü düşünün:
vektör < int > C = { 3 , iki , - 6 , 4 , 0 } ;
Maksimum toplamı olan dilim (alt dizi), toplam 5 veren {3, 2} dizisidir.
Aşağıdaki vektörü düşünün:
vektör < int > D = { 3 , iki , 6 , - 1 , 4 , 5 , - 1 , iki } ;
Maksimum toplamı olan alt dizi, toplam 20 veren {3, 2, 6, -1, 4, 5, -1, 2} dizisidir. Tüm dizidir.
Aşağıdaki vektörü düşünün:
vektör < int > E = { 5 , 7 , - 4 , - 10 , - 6 , 6 , 5 , 10 , - 5 , on beş , 4 , - 8 , - on beş , - 22 } ;
Burada maksimum toplamları olan iki alt dizi vardır. Daha yüksek toplam, maksimum alt dizi problemi için çözüm (cevap) olarak kabul edilendir. Alt diziler: {5, 7} toplamı 12 ve {6, 5, 10, -5, 15, 4} toplamı 35. Elbette, toplamı 35 olan dilim cevap.
Aşağıdaki vektörü düşünün:
vektör < int > F = { - 4 , 10 , on beş , 9 , - 5 , - yirmi , - 3 , - 12 , - 3 , 4 , 6 , 3 , iki , 8 , 3 , - 5 , - iki } ;
Maksimum toplamları olan iki alt dizi vardır. Daha yüksek toplam, maksimum alt dizi probleminin çözümü olarak kabul edilendir. Alt diziler: {10, 15, 9} toplamı 34 ve {4, 6, 3, 2, 8, 3} toplamı 26. Tabii ki, 34 toplamı olan dilim cevap çünkü sorun, daha yüksek toplamı olan alt diziyi değil, en yüksek toplamı olan alt diziyi aramaktır.
Kadane Algoritmasını Geliştirmek
Eğitimin bu bölümündeki bilgiler Kadane'nin orijinal çalışması değildir. Kadane'nin algoritmasını öğretmek yazarın kendi yöntemidir. Çalışan toplamlarıyla birlikte yukarıdaki vektörlerden biri bu tablodadır:
| Veri | 5 | 7 | -4 | -10 | -6 | 6 | 5 | 10 | -5 | on beş | 4 | -8 | -on beş | -22 |
| Toplam çalışan | 5 | 12 | 8 | -iki | -8 | -iki | 3 | 13 | 8 | 23 | 27 | yirmi bir | 16 | -6 |
| dizin | 0 | 1 | iki | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | on bir | 12 | 13 |
Bir dizin için Çalışan Toplam, dizin için olanlar da dahil olmak üzere önceki tüm değerlerin toplamıdır. Burada maksimum toplamları olan iki dizi vardır. Bunlar, 12 toplamını veren {5, 7} ve toplam 35 veren {6, 5, 10, -5, 15, 4}'dir. Toplamı 35 veren dizi istenen şeydir. .
Devam eden toplamlar için, 12 ve 27 değerleri olan iki tepe noktası olduğuna dikkat edin. Bu tepe noktaları, iki dizinin son dizinlerine karşılık gelir.
Dolayısıyla, Kadane'nin algoritmasının fikri, verilen dizide soldan sağa hareket ederek, karşılaştıkları maksimum toplamları karşılaştırırken çalışan toplamı yapmaktır.
Çalışan toplamları ile birlikte yukarıdan başka bir vektör bu tablodadır:
Maksimum toplamları olan iki dizi vardır. Bunlar {10, 15, 9} olup, toplam 34 verir; ve 26 toplamını veren {4, 6, 3, 2, 8, 3}. 34'ün toplamını veren dizi, istenen şeydir.
Devam eden toplamlar için, 30 ve 13 değerleri olan iki tepe noktası olduğuna dikkat edin. Bu tepe noktaları, iki dizinin son indekslerine karşılık gelir.
Yine, Kadane'nin algoritmasının fikri, verilen dizide soldan sağa hareket ederek, karşılaştıkları maksimum toplamları karşılaştırırken çalışan toplamı yapmaktır.
C++'da Kadane Algoritmasına göre kod
Makalenin bu bölümünde verilen kod, mutlaka Kadane'nin kullandığı kod değildir. Ancak, onun algoritması gereğidir. Diğer birçok C++ programı gibi program şu şekilde başlar:
#include#include
ad alanı std kullanarak;
Giriş ve çıkıştan sorumlu olan iostream kütüphanesinin dahil edilmesi vardır. Standart ad alanı kullanılır.
Kadane'nin algoritmasının fikri, verilen dizide soldan sağa hareket ederek karşılaştıkları maksimum toplamları karşılaştırırken çalışan toplamı elde etmektir. Algoritmanın işlevi:
int maxSunArray ( vektör < int > & A ) {int N = A.boyutu ( ) ;
int maxSum = A [ 0 ] ;
int runToplam = A [ 0 ] ;
için ( int i = 1 ; i < N; ben++ ) {
int tempRunTotal = runToplam + A [ i ] ; // A'dan küçük olabilir [ i ]
eğer ( A [ i ] > tempRunToplam )
runToplam = A [ i ] ; // içinde dava A [ i ] toplam çalışandan daha büyük
başka
runTotal = tempRunTotal;
eğer ( toplam > maxAmount ) // tüm maksimum toplamları karşılaştırmak
maxSum = çalışmaToplam;
}
dönüş maxMiktar;
}
Verilen dizinin (vektörün) N boyutu belirlenir. maxSum değişkeni, olası maksimum toplamlardan biridir. Bir dizinin en az bir maksimum toplamı vardır. runTotal değişkeni, her bir dizinde çalışan toplamı temsil eder. Her ikisi de dizinin ilk değeriyle başlatılır. Bu algoritmada, dizideki bir sonraki değer, değişen toplamdan büyükse, sonraki değer, yeni değişen toplam olacaktır.
Bir ana for döngüsü vardır. Tarama, verilen dizinin ilk öğesi olan maxSum ve runTotal değişkenlerinin A[0] olarak başlatılması nedeniyle sıfırdan değil 1'den başlar.
For döngüsünde, ilk ifade, önceki tüm değerlerin birikmiş toplamına mevcut değeri ekleyerek geçici bir toplam toplamı belirler.
Ardından, bir if/else yapısı var. Tek başına mevcut değer, o ana kadarki toplam değerden büyükse, bu tek değer, değişen toplam olur. Bu, özellikle verilen dizideki tüm değerler negatifse kullanışlıdır. Bu durumda, tek başına en yüksek negatif değer, maksimum değer (cevap) olacaktır. Geçerli değer tek başına o ana kadarki geçici toplamdan daha büyük değilse, o zaman değişen toplam önceki toplam artı mevcut değer olur - bu, if/else yapısının başka kısmıdır.
For döngüsündeki son kod segmenti, önceki bir dizi (alt dizi) için önceki herhangi bir maksimum toplam ile geçerli bir dizi için herhangi bir geçerli maksimum toplam arasında seçim yapar. Bu nedenle daha yüksek değer seçilir. Birden fazla maksimum alt dizi toplamı olabilir. Dizi soldan sağa tarandıkça, toplamın artacağını ve düşeceğini unutmayın. Negatif değerlerle karşılaştıkça düşer.
Son seçilen maksimum alt dizi toplamı, for döngüsünden sonra döndürülür.
Kadane'nin algoritma işlevi için uygun bir C++ ana işlevi içeriği:
vektör < int > bir = { 5 , - 7 , 3 , 5 , - iki , 4 , - 1 } ; // { 3 , 5 , - iki , 4 } - > 10int ret1 = maxSunArray ( A ) ;
cout << ret1 << son;
vektör < int > B = { - iki , 1 , - 3 , 4 , - 1 , iki , 1 , - 5 , 4 } ; // { 4 , - 1 , iki , 1 } - > 6
int ret2 = maxSunArray ( B ) ;
cout << ret2 << son;
vektör < int > C = { 3 , iki , - 6 , 4 , 0 } ; // { 3 , iki } - > 5
int ret3 = maxSunArray ( C ) ;
cout << ret3 << son;
vektör < int > D = { 3 , iki , 6 , - 1 , 4 , 5 , - 1 , iki } ; // { 3 , iki , 6 , - 1 , 4 , 5 , - 1 , iki } - > 5
int ret4 = maxSunArray ( D ) ;
cout << net4 << son;
vektör < int > E = { 5 , 7 , - 4 , - 10 , - 6 , 6 , 5 , 10 , - 5 , on beş , 4 , - 8 , - on beş , - 22 } ; // { 6 , 5 , 10 , - 5 , on beş , 4 } - > 35
int ret5 = maxSunArray ( VE ) ;
cout << ret5 << son;
vektör < int > F = { - 4 , 10 , on beş , 9 , - 5 , - yirmi , - 3 , - 12 , - 3 , 4 , 6 , 3 , iki , 8 , 3 , - 5 , - iki } ; // { 10 , on beş , 9 } - > 3. 4
int ret6 = maxSunArray ( F ) ;
cout << sağ 6 << son;
Bununla, çıktı olacaktır:
10
6
5
yirmi
35
3. 4
Buradaki her satır yanıtı, sırayla verilen bir diziye karşılık gelir.
Çözüm
Kadane algoritmasının zaman karmaşıklığı O(n)'dir; burada n, verilen dizideki eleman sayısıdır. Bu kez karmaşıklık, maksimum alt dizi sorunu için en hızlı olanıdır. Daha yavaş olan başka algoritmalar da var. Kadane'nin algoritmasının fikri, verilen dizide soldan sağa hareket ederek, karşılaştıkları maksimum toplamları karşılaştırırken çalışan toplamı yapmaktır. Mevcut değer tek başına o ana kadarki toplam değerden büyükse, bu tek değer yeni değişen toplam olur. Aksi takdirde, verilen dizi taranırken, yeni çalışan toplam, beklendiği gibi önceki çalışan toplam artı geçerli öğedir.
Farklı olası alt diziler için birden fazla maksimum toplam olabilir. Tüm olası alt diziler için en yüksek maksimum toplam seçilir.
Seçilen maksimum toplam aralığı için sınırlayıcı indeksler nelerdir? – Bu başka bir zaman için tartışma!
Chrys