Maximum Sub-Array Problem este aceeași cu Maximum Slice Problem. Acest tutorial discută problema codării în C++. Întrebarea este: care este suma maximă a oricărei succesiuni posibile de numere consecutive dintr-o matrice? Aceasta poate însemna întreaga matrice. Această problemă și soluția ei în orice limbă se numesc Problema maximă sub-matrice. Matricea poate avea posibile numere negative.
Soluția trebuie să fie eficientă. Trebuie să aibă cea mai rapidă complexitate de timp. De acum, cel mai rapid algoritm pentru soluție este cunoscut în comunitatea științifică ca algoritmul lui Kadane. Acest articol explică algoritmul lui Kadane cu C++.
Exemple de date
Luați în considerare următorul vector (matrice):
vector < int > A = { 5 , - 7 , 3 , 5 , - Două , 4 , - 1 } ;
Secțiunea (sub-matrice) cu suma maximă este șirul, {3, 5, -2, 4}, care dă o sumă de 10. Nicio altă secvență posibilă, chiar și întreaga matrice, nu va da o sumă de până la valoarea 10. Întregul tablou dă o sumă de 7, care nu este suma maximă.
Luați în considerare următorul vector:
vector < int > B = { - Două , 1 , - 3 , 4 , - 1 , Două , 1 , - 5 , 4 } ;
Secțiunea (sub-matrice) cu suma maximă este secvența, {4, −1, 2, 1} care dă o sumă de 6. Rețineți că pot exista numere negative în cadrul sub-matrice pentru suma maximă.
Luați în considerare următorul vector:
vector < int > C = { 3 , Două , - 6 , 4 , 0 } ;
Secțiunea (sub-matrice) cu suma maximă este secvența, {3, 2} care dă o sumă de 5.
Luați în considerare următorul vector:
vector < int > D = { 3 , Două , 6 , - 1 , 4 , 5 , - 1 , Două } ;
Sub-matricea cu suma maximă este șirul, {3, 2, 6, -1, 4, 5, -1, 2} care dă o sumă de 20. Este întregul tablou.
Luați în considerare următorul vector:
vector < int > E = { 5 , 7 , - 4 , - 10 , - 6 , 6 , 5 , 10 , - 5 , cincisprezece , 4 , - 8 , - cincisprezece , - 22 } ;
Există două sub-matrice cu sume maxime, aici. Suma mai mare este cea care este considerată ca soluție (răspuns) pentru problema sub-matricei maxime. Sub-matricele sunt: {5, 7} cu o sumă de 12 și {6, 5, 10, -5, 15, 4} cu o sumă de 35. Desigur, felia cu suma de 35, este răspunsul.
Luați în considerare următorul vector:
vector < int > F = { - 4 , 10 , cincisprezece , 9 , - 5 , - douăzeci , - 3 , - 12 , - 3 , 4 , 6 , 3 , Două , 8 , 3 , - 5 , - Două } ;
Există două sub-matrice cu sume maxime. Suma mai mare este cea care este considerată soluție pentru problema sub-matricei maxime. Sub-matricele sunt: {10, 15, 9} cu o sumă de 34 și {4, 6, 3, 2, 8, 3} cu o sumă de 26. Desigur, felia cu suma de 34 este răspunsul pentru că problema este să căutați sub-matricea cu suma cea mai mare și nu sub-matricea cu suma mai mare.
Dezvoltarea algoritmului lui Kadane
Informațiile din această secțiune a tutorialului nu sunt lucrarea originală de la Kadane. Este modul propriu al autorului de a preda algoritmul lui Kadane. Unul dintre vectorii de mai sus, cu totalurile sale, se află în acest tabel:
| Date | 5 | 7 | -4 | -10 | -6 | 6 | 5 | 10 | -5 | cincisprezece | 4 | -8 | -cincisprezece | -22 |
| Total curent | 5 | 12 | 8 | -Două | -8 | -Două | 3 | 13 | 8 | 23 | 27 | douăzeci și unu | 16 | -6 |
| index | 0 | 1 | Două | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | unsprezece | 12 | 13 |
Totalul curent pentru un index este suma tuturor valorilor anterioare, inclusiv cea pentru index. Există două secvențe cu sume maxime aici. Ele sunt {5, 7}, care dă o sumă de 12, și {6, 5, 10, -5, 15, 4}, care dă o sumă de 35. Secvența care dă o sumă de 35 este ceea ce se dorește .
Observați că pentru totalurile cumulate, există două vârfuri care sunt valorile, 12 și 27. Aceste vârfuri corespund ultimilor indici ai celor două secvențe.
Deci, ideea algoritmului lui Kadane este de a face totalul în timp ce comparăm sumele maxime pe măsură ce acestea sunt întâlnite, deplasându-se de la stânga la dreapta în matricea dată.
Un alt vector de sus, cu totalurile sale curente, este în acest tabel:
Există două secvențe cu sume maxime. Sunt {10, 15, 9}, ceea ce dă o sumă de 34; și {4, 6, 3, 2, 8, 3} care dă o sumă de 26. Secvența care dă suma de 34 este ceea ce se dorește.
Observați că pentru totalurile curente, există două vârfuri care sunt valorile, 30 și 13. Aceste vârfuri corespund ultimilor indici ai celor două secvențe.
Din nou, ideea algoritmului lui Kadane este de a face totalul în timp ce comparăm sumele maxime pe măsură ce acestea sunt întâlnite, deplasându-se de la stânga la dreapta în matricea dată.
Cod prin algoritmul lui Kadane în C++
Codul dat în această secțiune a articolului nu este neapărat ceea ce a folosit Kadane. Cu toate acestea, este după algoritmul său. Programul, ca multe alte programe C++, ar începe cu:
#include#include
folosind namespace std;
Există includerea bibliotecii iostream, care este responsabilă pentru intrare și ieșire. Se folosește spațiul de nume standard.
Ideea algoritmului lui Kadane este de a avea totalul curent în timp ce se compară sumele maxime pe măsură ce acestea sunt întâlnite, deplasându-se de la stânga la dreapta în matricea dată. Funcția pentru algoritm este:
int maxSunArray ( vector < int > & A ) {int N = A.mărime ( ) ;
int maxSum = A [ 0 ] ;
int runTotal = A [ 0 ] ;
pentru ( int i = 1 ; i < N; i++ ) {
int tempRunTotal = runTotal + A [ i ] ; // ar putea fi mai mic decât A [ i ]
dacă ( A [ i ] > tempRunTotal )
runTotal = A [ i ] ; // în caz A [ i ] este mai mare decât totalul curent
altfel
runTotal = tempRunTotal;
dacă ( runTotal > maxAmount ) // comparând toate sumele maxime
maxSum = runTotal;
}
întoarcere maxAmount;
}
Se determină dimensiunea, N a tabloului dat (vector). Variabila, maxSum este una dintre sumele maxime posibile. O matrice are cel puțin o sumă maximă. Variabila runTotal reprezintă totalul curent la fiecare index. Ambele sunt inițializate cu prima valoare a matricei. În acest algoritm, dacă următoarea valoare din matrice este mai mare decât totalul curent, atunci următoarea valoare va deveni noul total curent.
Există o singură buclă principală. Scanarea începe de la 1 și nu de la zero din cauza inițializării variabilelor, maxSum și runTotal la A[0] care este primul element al matricei date.
În bucla for, prima instrucțiune determină un total curent temporar prin adăugarea valorii curente la suma acumulată a tuturor valorilor anterioare.
În continuare, există un construct dacă/altfel. Dacă valoarea curentă este mai mare decât totalul curent de până acum, atunci acea valoare unică devine totalul cumulat. Acest lucru este util mai ales dacă toate valorile din matricea dată sunt negative. În acest caz, numai cea mai mare valoare negativă va deveni valoarea maximă (răspunsul). Dacă valoarea curentă singură nu este mai mare decât totalul curent temporar de până acum, atunci totalul cumulat devine totalul curent anterior plus valoarea curentă, aceasta este partea else-parte a constructului if/else.
Ultimul segment de cod din bucla for alege între orice sumă maximă anterioară pentru o secvență anterioară (sub-matrice) și orice sumă maximă curentă pentru o secvență curentă. Prin urmare, se alege valoarea mai mare. Poate exista mai mult de o sumă maximă de sub-matrice. Rețineți că totalul curent ar crește și scădea, deoarece matricea este scanată de la stânga la dreapta. Se cade pe măsură ce întâlnește valori negative.
Suma maximă finală ale sub-matricei este returnată după bucla for.
Conținutul pentru o funcție principală C++ adecvată, pentru funcția de algoritm a lui Kadane este:
vector < int > A = { 5 , - 7 , 3 , 5 , - Două , 4 , - 1 } ; // { 3 , 5 , - Două , 4 } - > 10int ret1 = maxSunArray ( A ) ;
cout << ret1 << endl;
vector < int > B = { - Două , 1 , - 3 , 4 , - 1 , Două , 1 , - 5 , 4 } ; // { 4 , − 1 , Două , 1 } - > 6
int ret2 = maxSunArray ( B ) ;
cout << ret2 << endl;
vector < int > C = { 3 , Două , - 6 , 4 , 0 } ; // { 3 , Două } - > 5
int ret3 = maxSunArray ( C ) ;
cout << ret3 << endl;
vector < int > D = { 3 , Două , 6 , - 1 , 4 , 5 , - 1 , Două } ; // { 3 , Două , 6 , - 1 , 4 , 5 , - 1 , Două } - > 5
int ret4 = maxSunArray ( D ) ;
cout << net4 << endl;
vector < int > E = { 5 , 7 , - 4 , - 10 , - 6 , 6 , 5 , 10 , - 5 , cincisprezece , 4 , - 8 , - cincisprezece , - 22 } ; // { 6 , 5 , 10 , - 5 , cincisprezece , 4 } - > 35
int ret5 = maxSunArray ( ȘI ) ;
cout << ret5 << endl;
vector < int > F = { - 4 , 10 , cincisprezece , 9 , - 5 , - douăzeci , - 3 , - 12 , - 3 , 4 , 6 , 3 , Două , 8 , 3 , - 5 , - Două } ; // { 10 , cincisprezece , 9 } - > 3. 4
int ret6 = maxSunArray ( F ) ;
cout << corect 6 << endl;
Cu aceasta, rezultatul va fi:
10
6
5
douăzeci
35
3. 4
Fiecare răspuns de linie de aici corespunde unui tablou dat, în ordine.
Concluzie
Complexitatea timpului pentru algoritmul lui Kadane este O(n), unde n este numărul de elemente din tabloul dat. Această complexitate de timp este cea mai rapidă pentru problema maximă sub-matrice. Există și alți algoritmi care sunt mai lenți. Ideea algoritmului lui Kadane este de a face totalul, comparând în același timp sumele maxime pe măsură ce acestea sunt întâlnite, deplasându-se de la stânga la dreapta în matricea dată. Dacă doar valoarea curentă este mai mare decât totalul curent de până acum, atunci acea valoare unică devine noul total cumulat. În caz contrar, noul total curent este totalul curent anterior plus elementul curent, așa cum era anticipat, pe măsură ce matricea dată este scanată.
Pot exista mai multe sume maxime, pentru diferite sub-matrice posibile. Se alege cea mai mare sumă maximă, pentru toate sub-matricele posibile.
Care sunt indicii limitatori pentru intervalul sumei maxime alese? – Asta e discuție pentru altă dată!
Chrys