Maksymalny problem z podaracją w C ++

Maksymalny problem z podaracją jest taki sam, jak maksymalny problem plastra. Ten samouczek omawia problem z kodowaniem w C++. Pytanie brzmi: jaka jest maksymalna suma każdej możliwej sekwencji kolejnych liczb w ramach tablicy? Może to oznaczać całą tablicę. Ten problem i jego rozwiązanie w dowolnym języku jest określane jako maksymalny problem podrzędny. Tablica może mieć możliwe liczby ujemne.

Rozwiązanie musi być wydajne. Musi mieć najszybszą złożoność czasu. Na razie najszybszy algorytm rozwiązania jest znany w społeczności naukowej jako algorytm Kadane. Ten artykuł wyjaśnia algorytm Kadane z C++.

Przykłady danych

Rozważ następujący wektor (tablica):

wektor A = 5, -7, 3, 5, -2, 4, -1;

Slice (pod -podorządek) z maksymalną sumą jest sekwencja, 3, 5, -2, 4, która podaje sumę 10. Żadna inna możliwa sekwencja, nawet cała tablica, nie da suma wartości 10. Cała tablica podaje sumę 7, co nie jest maksymalną sumą.

Rozważ następujący wektor:

wektor B = -2, 1, -3, 4, -1, 2, 1, -5, 4;

Slice (podarray) z maksymalną sumą jest sekwencja, 4, −1, 2, 1, która podaje sumę 6. Należy zauważyć, że w podręczniku mogą istnieć liczby ujemne dla maksymalnej sumy.

Rozważ następujący wektor:

wektor C = 3, 2, -6, 4, 0;

Slice (sub-array) z maksymalną sumą jest sekwencja, 3, 2, która podaje sumę 5.

Rozważ następujący wektor:

wektor D = 3, 2, 6, -1, 4, 5, -1, 2;

Podręcznik z maksymalną sumą jest sekwencja, 3, 2, 6, -1, 4, 5, -1, 2, która daje sumę 20. To jest cała tablica.

Rozważ następujący wektor:

wektor E = 5, 7, -4, -10, -6, 6, 5, 10, -5, 15, 4, -8, -15, -22;

Istnieją dwa pod-pod-ramy o maksymalnych sumach, tutaj. Wyższa suma to ta, która jest uważana za rozwiązanie (odpowiedź) dla maksymalnego problemu podrzędnego. Sub -arrays to: 5, 7 z sumą 12 i 6, 5, 10, -5, 15, 4 z sumą 35. Oczywiście, plasterem z sumą 35, jest odpowiedzią.

Rozważ następujący wektor:

wektor F = -4, 10, 15, 9, -5, -20, -3, -12, -3, 4, 6, 3, 2, 8, 3, -5, -2;

Istnieją dwa pod-pod-ramy o maksymalnych sumach. Wyższa suma to ta, która jest uważana za rozwiązanie dla maksymalnego problemu podrzędnego. Sub-loarray to: 10, 15, 9 z sumą 34 i 4, 6, 3, 2, 8, 3 z sumą 26. Oczywiście plasterze z sumą 34 jest odpowiedzią, ponieważ problemem jest poszukiwanie podataku z najwyższą sumą, a nie pod-podorządkową z wyższą sumą.

Opracowanie algorytmu Kadane

Informacje w tym rozdziale samouczka nie są oryginalnym dziełem Kadane. Jest to własny sposób nauczania algorytmu Kadane. Jeden z powyższych wektorów, z jego sumami biegowymi, znajduje się w tej tabeli:

Uruchomienie całkowitej dla indeksu jest sumą wszystkich poprzednich wartości, w tym dla indeksu. Istnieją dwie sekwencje o maksymalnych sumach. Są 5, 7, które podaje sumę 12 i 6, 5, 10, -5, 15, 4, co daje sumę 35. Sekwencja, która daje sumę 35, jest pożądana.

Zauważ, że dla sum bieżących istnieją dwa szczyty, które są wartościami, 12 i 27. Te piki odpowiadają ostatnim indeksom dwóch sekwencji.

Tak więc idea algorytmu Kadane polega na wykonywaniu całkowitej całkowitej liczby podczas porównywania maksymalnych sum podczas ich napotkania, przechodzącym od lewej do prawej w danej tablicy.

Kolejny wektor z góry, z jego sumami biegowymi, znajduje się w tej tabeli:

Istnieją dwie sekwencje o maksymalnych sumach. Są one 10, 15, 9, co daje sumę 34; i 4, 6, 3, 2, 8, 3, co daje sumę 26. Sekwencja, która daje sumę 34, jest pożądana.

Zauważ, że dla sum bieżących istnieją dwa szczyty, które są wartościami, 30 i 13. Te piki odpowiadają ostatnim indeksom dwóch sekwencji.

Ponownie, ideą algorytmu Kadane'a polega na wykonywaniu całkowitej całkowitej bieżących, porównując maksymalne sumy podczas ich napotkania, przechodząc od lewej do prawej w danej tablicy.

Kod autorstwa algorytmu Kadane w C++

Kod podany w niniejszej sekcji artykułu niekoniecznie jest tym, czego użył Kadane. Jest to jednak jego algorytm. Program taki jak wiele innych programów C ++ zacząłby się od:

#włączać
#włączać

za pomocą przestrzeni nazw Std;

Istnieje włączenie biblioteki iostream, która jest odpowiedzialna za dane wejściowe i wyjściowe. Standardowa przestrzeń nazw jest używana.

Ideą algorytmu Kadane'a jest posiadanie całkowitej całkowitej liczby podczas porównywania maksymalnych sum podczas ich napotkania, przechodząc od lewej do prawej w danej tablicy. Funkcja algorytmu to:

int maxsunarray (wektor &A)
int n = a.rozmiar();
int maxsum = a [0];
int runtotal = a [0];
dla (int i = 1; i < N; i++)
int tempruntotal = runtotal + a [i]; // może być mniejsze niż [i]
if ([i]> tempruntotal)
RUNTOTAL = A [i]; // na wypadek, gdyby [i] jest większy niż bieganie
w przeciwnym razie
runtotal = tempruntotal;
if (runtotal> maxsum) // Porównanie wszystkich maksymalnych sum
maxsum = runtotal;

return maxsum;

Rozmiar, n danej tablicy (wektor) jest określony. Zmienna, maksymalna jest jedną z możliwych maksymalnych sum. Tablica ma co najmniej jedną maksymalną sumę. Zmienna, Runtotal reprezentuje całkowitą sumę w każdym indeksie. Oba są inicjowane z pierwszą wartością tablicy. W tym algorytmie, jeśli następna wartość w tablicy jest większa niż w sumie działającej, następna wartość stanie się nową całkowitą sumą.

Jest jeden główny na pętlę. Skanowanie rozpoczyna się od 1, a nie zera z powodu inicjalizacji zmiennych, maksymum i runtotal do [0], które pierwszy element danej tablicy.

W przypadku pętli pierwsze oświadczenie określa tymczasową sumę działań, dodając bieżącą wartość do zgromadzonej sumie wszystkich poprzednich wartości.

Następnie istnieje konstrukt IF/Else. Jeśli sama bieżąca wartość jest większa niż do tej pory, wówczas ta pojedyncza wartość staje się całkowitą sumą. Jest to przydatne, zwłaszcza jeśli wszystkie wartości w danej tablicy są ujemne. W takim przypadku sama najwyższa wartość ujemna stanie się wartością maksymalną (odpowiedź). Jeśli sama bieżąca wartość nie jest większa niż tymczasowa suma działająca do tej pory, wówczas całkowita całkowita liczba staje się poprzednią całkowitą sumą plus bieżącą wartość, - to część konstrukcji if/else konstrukcja.

Ostatni segment kodu w pętli wybiera między dowolną poprzednią maksymalną sumą dla poprzedniej sekwencji (subarray) a dowolną bieżącą maksymalną sumą dla bieżącej sekwencji. Dlatego wyższa wartość jest wybierana. Może być więcej niż jedna maksymalna suma podrzędnej. Zwróć uwagę, że suma biegania wzrośnie i spadnie, ponieważ tablica jest skanowana od lewej do prawej. Spada, ponieważ spełnia wartości ujemne.

Ostateczna wybrana maksymalna suma podrzędna jest zwracana po pętli.

Treść odpowiedniej funkcji głównej C ++ dla funkcji algorytmu Kadane jest:

wektor A = 5, -7, 3, 5, -2, 4, -1; // 3, 5, -2, 4 -> 10
int ret1 = maxsunarray (a);
Cout << ret1 << endl;
wektor B = -2, 1, -3, 4, -1, 2, 1, -5, 4; // 4, −1, 2, 1 -> 6
int ret2 = maxsunarray (b);
Cout << ret2 << endl;
wektor C = 3, 2, -6, 4, 0; // 3, 2 -> 5
int ret3 = maxsunarray (c);
Cout << ret3 << endl;
wektor D = 3, 2, 6, -1, 4, 5, -1, 2; // 3, 2, 6, -1, 4, 5, -1, 2 -> 5
int ret4 = maxsunarray (d);
Cout << ret4 << endl;
wektor E = 5, 7, -4, -10, -6, 6, 5, 10, -5, 15, 4, -8, -15, -22; // 6, 5, 10, -5, 15, 4 -> 35
int ret5 = maxsunarray (e);
Cout << ret5 << endl;
wektor F = -4, 10, 15, 9, -5, -20, -3, -12, -3, 4, 6, 3, 2, 8, 3, -5, -2; // 10, 15, 9-> 34
int ret6 = maxsunarray (f);
Cout << ret6 << endl;

Z tym wyjściem będzie:

10

6

5

20

35

34

Każda odpowiedź na linię tutaj, odpowiada danej tablicy, w kolejności.

Wniosek

Złożoność czasu dla algorytmu Kadane'a wynosi O (n), gdzie n jest liczbą elementów w danej tablicy. Ta złożoność czasu jest najszybsza dla maksymalnego problemu podrzędnego. Istnieją inne algorytmy, które są wolniejsze. Ideą algorytmu Kadane'a jest wykonywanie całkowitej całkowitej bieżą, jedno. Jeśli sama bieżąca wartość jest większa niż do tej pory, wówczas ta pojedyncza wartość staje się nową całkowitą sumą. W przeciwnym razie nowa suma działająca jest poprzednią całkowitą sumą plus bieżący element, zgodnie z przewidywaniami, jak podana tablica jest skanowana.

Może być więcej niż jedna maksymalna suma, dla różnych możliwych pod-pod-pod-podoch. Wybierana jest najwyższa maksymalna suma, dla wszystkich możliwych pod-pod-nowoczesnych.

Jakie są wskaźniki ograniczające dla zakresu wybranej maksymalnej sumy? - To jest dyskusja od jakiegoś czasu!

Chrys