Ang Maximum Sub-Array Problem ay kapareho ng Maximum Slice Problem. Tinatalakay ng tutorial na ito ang problema sa coding sa C++. Ang tanong ay: ano ang pinakamataas na kabuuan ng anumang posibleng pagkakasunod-sunod ng magkakasunod na numero sa loob ng isang array? Ito ay maaaring mangahulugan ng buong array. Ang problemang ito at ang solusyon nito sa anumang wika, ay tinutukoy bilang Maximum Sub-Array Problem. Ang array ay maaaring magkaroon ng mga posibleng negatibong numero.
Ang solusyon ay dapat na mahusay. Kailangan itong magkaroon ng pinakamabilis na pagiging kumplikado ng oras. Sa ngayon, ang pinakamabilis na algorithm para sa solusyon ay kilala sa siyentipikong komunidad bilang Kadane's Algorithm. Ipinapaliwanag ng artikulong ito ang algorithm ng Kadane sa C++.
Mga Halimbawa ng Data
Isaalang-alang ang sumusunod na vector (array):
vector < int > A = { 5 , - 7 , 3 , 5 , - dalawa , 4 , - 1 } ;
Ang slice (sub-array) na may pinakamataas na kabuuan ay ang sequence, {3, 5, -2, 4}, na nagbibigay ng kabuuan na 10. Walang ibang posibleng sequence, kahit ang buong array, ay magbibigay ng kabuuan ng hanggang ang halaga ng 10. Ang buong array ay nagbibigay ng kabuuan na 7, na hindi ang pinakamataas na kabuuan.
Isaalang-alang ang sumusunod na vector:
vector < int > B = { - dalawa , 1 , - 3 , 4 , - 1 , dalawa , 1 , - 5 , 4 } ;
Ang slice (sub-array) na may maximum na kabuuan ay ang sequence, {4, −1, 2, 1} na nagbibigay ng kabuuan na 6. Tandaan na maaaring mayroong mga negatibong numero sa loob ng sub-array para sa maximum na kabuuan.
Isaalang-alang ang sumusunod na vector:
vector < int > C = { 3 , dalawa , - 6 , 4 , 0 } ;
Ang slice (sub-array) na may pinakamataas na kabuuan ay ang sequence, {3, 2} na nagbibigay ng kabuuan na 5.
Isaalang-alang ang sumusunod na vector:
vector < int > D = { 3 , dalawa , 6 , - 1 , 4 , 5 , - 1 , dalawa } ;
Ang sub-array na may pinakamataas na kabuuan ay ang sequence, {3, 2, 6, -1, 4, 5, -1, 2} na nagbibigay ng kabuuan na 20. Ito ang buong array.
Isaalang-alang ang sumusunod na vector:
vector < int > E = { 5 , 7 , - 4 , - 10 , - 6 , 6 , 5 , 10 , - 5 , labinlima , 4 , - 8 , - labinlima , - 22 } ;
Mayroong dalawang sub-array na may pinakamataas na kabuuan, dito. Ang mas mataas na kabuuan ay ang isa na itinuturing na solusyon (sagot) para sa maximum na sub-array na problema. Ang mga sub-array ay: {5, 7} na may kabuuan na 12, at {6, 5, 10, -5, 15, 4} na may kabuuan na 35. Siyempre, ang slice na may kabuuan na 35, ay ang sagot.
Isaalang-alang ang sumusunod na vector:
vector < int > F = { - 4 , 10 , labinlima , 9 , - 5 , - dalawampu , - 3 , - 12 , - 3 , 4 , 6 , 3 , dalawa , 8 , 3 , - 5 , - dalawa } ;
Mayroong dalawang sub-array na may pinakamataas na kabuuan. Ang mas mataas na kabuuan ay ang isa na itinuturing na solusyon para sa maximum na sub-array na problema. Ang mga sub-array ay: {10, 15, 9} na may kabuuan na 34, at {4, 6, 3, 2, 8, 3} na may kabuuan na 26. Siyempre, ang slice na may kabuuan na 34 ay ang sagot dahil ang problema ay hanapin ang sub-array na may pinakamataas na sum at hindi ang sub-array na may mas mataas na sum.
Pagbuo ng Algorithm ng Kadane
Ang impormasyon sa seksyong ito ng tutorial ay hindi orihinal na gawa mula sa Kadane. Ito ang sariling paraan ng may-akda upang ituro ang algorithm ng Kadane. Ang isa sa mga vector sa itaas, kasama ang mga tumatakbong kabuuan, ay nasa talahanayang ito:
| Data | 5 | 7 | -4 | -10 | -6 | 6 | 5 | 10 | -5 | labinlima | 4 | -8 | -labing lima | -22 |
| Running Total | 5 | 12 | 8 | -dalawa | -8 | -dalawa | 3 | 13 | 8 | 23 | 27 | dalawampu't isa | 16 | -6 |
| index | 0 | 1 | dalawa | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | labing-isa | 12 | 13 |
Ang Running Total para sa isang index ay ang kabuuan ng lahat ng nakaraang mga halaga kasama ang para sa index. Mayroong dalawang sequence na may pinakamataas na kabuuan dito. Ang mga ito ay {5, 7}, na nagbibigay ng kabuuan ng 12, at {6, 5, 10, -5, 15, 4}, na nagbibigay ng kabuuan ng 35. Ang sequence na nagbibigay ng kabuuan ng 35 ay kung ano ang nais .
Pansinin na para sa mga kabuuang tumatakbo, mayroong dalawang peak na siyang mga value, 12 at 27. Ang mga peak na ito ay tumutugma sa mga huling index ng dalawang sequence.
Kaya, ang ideya ng algorithm ng Kadane ay ang paggawa ng kabuuang tumatakbo habang inihahambing ang maximum na mga kabuuan habang nakatagpo ang mga ito, lumilipat mula kaliwa pakanan sa ibinigay na array.
Ang isa pang vector mula sa itaas, kasama ang mga tumatakbong kabuuan nito, ay nasa talahanayang ito:
Mayroong dalawang sequence na may pinakamataas na kabuuan. Ang mga ito ay {10, 15, 9}, na nagbibigay ng kabuuan na 34; at {4, 6, 3, 2, 8, 3} na nagbibigay ng kabuuan ng 26. Ang sequence na nagbibigay ng kabuuan ng 34, ay kung ano ang ninanais.
Pansinin na para sa mga kabuuang tumatakbo, mayroong dalawang peak na siyang mga value, 30 at 13. Ang mga peak na ito ay tumutugma sa mga huling index ng dalawang sequence.
Muli, ang ideya ng algorithm ng Kadane ay ang paggawa ng kabuuang tumatakbo habang inihahambing ang maximum na mga kabuuan habang sila ay nakatagpo, lumilipat mula kaliwa pakanan sa ibinigay na array.
Code ng Kadane's Algorithm sa C++
Ang code na ibinigay sa seksyong ito ng artikulo ay hindi kinakailangan kung ano ang ginamit ni Kadane. Gayunpaman, ito ay sa pamamagitan ng kanyang algorithm. Ang programa tulad ng maraming iba pang mga C++ na programa, ay magsisimula sa:
#include#include
gamit ang namespace std;
Mayroong pagsasama ng iostream library, na responsable para sa input at output. Ginagamit ang karaniwang namespace.
Ang ideya ng algorithm ng Kadane ay ang pagkakaroon ng kabuuang tumatakbo habang inihahambing ang maximum na mga kabuuan habang sila ay nakatagpo, lumilipat mula kaliwa pakanan sa ibinigay na array. Ang function para sa algorithm ay:
int maxSunArray ( vector < int > at A ) {int N = A.laki ( ) ;
int maxSum = A [ 0 ] ;
int runTotal = A [ 0 ] ;
para sa ( int i = 1 ; i < N; i++ ) {
int tempRunTotal = runTotal + A [ i ] ; // maaaring mas maliit sa A [ i ]
kung ( A [ i ] > tempRunTotal )
runTotal = A [ i ] ; // sa kaso A [ i ] ay mas malaki kaysa sa kabuuang tumatakbo
iba pa
runTotal = tempRunTotal;
kung ( runTotal > maxAmount ) // paghahambing ng lahat ng pinakamataas na kabuuan
maxSum = runTotal;
}
bumalik maxAmount;
}
Ang laki, N ng ibinigay na array (vector) ay tinutukoy. Ang variable, maxSum ay isa sa mga posibleng maximum sums. Ang isang array ay may hindi bababa sa isang maximum na kabuuan. Ang variable, runTotal ay kumakatawan sa kabuuang tumatakbo sa bawat index. Pareho silang sinisimulan sa unang halaga ng array. Sa algorithm na ito, kung ang susunod na halaga sa array ay mas malaki kaysa sa kabuuang tumatakbo, ang susunod na halaga ay magiging bagong kabuuang tumatakbo.
Mayroong isang pangunahing para-loop. Ang pag-scan ay nagsisimula sa 1 at hindi zero dahil sa pagsisimula ng mga variable, maxSum at runTotal hanggang A[0] na siyang unang elemento ng ibinigay na array.
Sa for-loop, tinutukoy ng unang statement ang isang pansamantalang kabuuang tumatakbo sa pamamagitan ng pagdaragdag ng kasalukuyang halaga sa naipon na kabuuan ng lahat ng nakaraang halaga.
Susunod, mayroong isang if/else construct. Kung ang kasalukuyang halaga lamang ay mas malaki kaysa sa kabuuang tumatakbo sa ngayon, ang solong halaga na iyon ang magiging kabuuang tumatakbo. Ito ay madaling gamitin lalo na kung ang lahat ng mga halaga sa ibinigay na array ay negatibo. Sa kasong ito, ang pinakamataas na negatibong halaga lamang ang magiging pinakamataas na halaga (ang sagot). Kung ang kasalukuyang halaga lamang ay hindi mas malaki kaysa sa pansamantalang kabuuang pagpapatakbo sa ngayon, ang kabuuang tumatakbo ay magiging dating kabuuang tumatakbo kasama ang kasalukuyang halaga, - ito ang ibang bahagi ng kung/ibang konstruksyon.
Ang huling segment ng code sa for-loop ay pumipili sa pagitan ng anumang nakaraang maximum na kabuuan para sa isang nakaraang sequence (sub-array) at anumang kasalukuyang maximum na kabuuan para sa isang kasalukuyang sequence. Ang mas mataas na halaga ay pinili. Maaaring mayroong higit sa isang maximum na sub-array sum. Tandaan na ang kabuuang tumatakbo ay tataas at bababa, dahil ang array ay ini-scan mula kaliwa hanggang kanan. Bumabagsak ito habang nakakatugon sa mga negatibong halaga.
Ang huling napiling maximum sub-array sum ay ibinalik pagkatapos ng for-loop.
Ang nilalaman para sa isang angkop na pangunahing function ng C++, para sa function ng algorithm ng Kadane ay:
vector < int > A = { 5 , - 7 , 3 , 5 , - dalawa , 4 , - 1 } ; // { 3 , 5 , - dalawa , 4 } - > 10int ret1 = maxSunArray ( A ) ;
cout << ret1 << endl;
vector < int > B = { - dalawa , 1 , - 3 , 4 , - 1 , dalawa , 1 , - 5 , 4 } ; // { 4 , − 1 , dalawa , 1 } - > 6
int ret2 = maxSunArray ( B ) ;
cout << ret2 << endl;
vector < int > C = { 3 , dalawa , - 6 , 4 , 0 } ; // { 3 , dalawa } - > 5
int ret3 = maxSunArray ( C ) ;
cout << ret3 << endl;
vector < int > D = { 3 , dalawa , 6 , - 1 , 4 , 5 , - 1 , dalawa } ; // { 3 , dalawa , 6 , - 1 , 4 , 5 , - 1 , dalawa } - > 5
int ret4 = maxSunArray ( D ) ;
cout << net4 << endl;
vector < int > E = { 5 , 7 , - 4 , - 10 , - 6 , 6 , 5 , 10 , - 5 , labinlima , 4 , - 8 , - labinlima , - 22 } ; // { 6 , 5 , 10 , - 5 , labinlima , 4 } - > 35
int ret5 = maxSunArray ( AT ) ;
cout << ret5 << endl;
vector < int > F = { - 4 , 10 , labinlima , 9 , - 5 , - dalawampu , - 3 , - 12 , - 3 , 4 , 6 , 3 , dalawa , 8 , 3 , - 5 , - dalawa } ; // { 10 , labinlima , 9 } - > 3. 4
int ret6 = maxSunArray ( F ) ;
cout << tama 6 << endl;
Sa pamamagitan nito, ang magiging output ay:
10
6
5
dalawampu
35
3. 4
Ang bawat sagot sa linya dito, ay tumutugma sa isang naibigay na array, sa pagkakasunud-sunod.
Konklusyon
Ang pagiging kumplikado ng oras para sa algorithm ng Kadane ay O(n), kung saan ang n ay ang bilang ng mga elemento sa ibinigay na array. Ang pagiging kumplikado ng oras na ito ay ang pinakamabilis para sa maximum na problema sa sub-array. Mayroong iba pang mga algorithm na mas mabagal. Ang ideya ng algorithm ng Kadane ay ang paggawa ng kabuuang tumatakbo, habang inihahambing ang maximum na mga kabuuan habang nakatagpo ang mga ito, lumilipat mula kaliwa pakanan sa ibinigay na array. Kung ang kasalukuyang halaga lamang ay mas malaki kaysa sa kabuuang tumatakbo sa ngayon, ang solong halaga na iyon ang magiging bagong kabuuang tumatakbo. Kung hindi, ang bagong kabuuang tumatakbo ay ang dating kabuuang tumatakbo kasama ang kasalukuyang elemento, gaya ng inaasahan, habang ang ibinigay na array ay na-scan.
Maaaring mayroong higit sa isang maximum na kabuuan, para sa iba't ibang posibleng sub-array. Ang pinakamataas na maximum na kabuuan, para sa lahat ng posibleng mga sub-array, ay pinili.
Ano ang mga naglilimitang index para sa hanay ng napiling maximum na kabuuan? - Iyon ay talakayan para sa ibang pagkakataon!
Chrys