గరిష్ట ఉప-శ్రేణి సమస్య గరిష్ట స్లైస్ సమస్య వలె ఉంటుంది. ఈ ట్యుటోరియల్ C++లో కోడింగ్ సమస్య గురించి చర్చిస్తుంది. ప్రశ్న ఏమిటంటే: శ్రేణిలోని వరుస సంఖ్యల యొక్క ఏదైనా సాధ్యమైన శ్రేణి యొక్క గరిష్ట మొత్తం ఎంత? ఇది మొత్తం శ్రేణిని సూచిస్తుంది. ఈ సమస్య మరియు దాని పరిష్కారాన్ని ఏ భాషలోనైనా గరిష్ట ఉప-శ్రేణి సమస్యగా సూచిస్తారు. శ్రేణి ప్రతికూల సంఖ్యలను కలిగి ఉండవచ్చు.
పరిష్కారం సమర్థవంతంగా ఉండాలి. ఇది వేగవంతమైన సమయ సంక్లిష్టతను కలిగి ఉండాలి. ప్రస్తుతానికి, పరిష్కారం కోసం వేగవంతమైన అల్గారిథమ్‌ను శాస్త్రీయ సమాజంలో కడనే యొక్క అల్గోరిథం అని పిలుస్తారు. ఈ కథనం C++తో Kadane యొక్క అల్గారిథమ్‌ను వివరిస్తుంది.
డేటా ఉదాహరణలు
కింది వెక్టర్ (శ్రేణి)ని పరిగణించండి:
వెక్టర్ < int > A = { 5 , - 7 , 3 , 5 , - రెండు , 4 , - 1 } ;
గరిష్ట మొత్తంతో కూడిన స్లైస్ (ఉప-శ్రేణి) క్రమం, {3, 5, -2, 4}, ఇది 10 మొత్తాన్ని ఇస్తుంది. ఏ ఇతర సాధ్యమైన క్రమం, మొత్తం శ్రేణి కూడా గరిష్ట మొత్తాన్ని ఇవ్వదు 10 యొక్క విలువ. మొత్తం శ్రేణి 7 మొత్తాన్ని ఇస్తుంది, ఇది గరిష్ట మొత్తం కాదు.
కింది వెక్టర్‌ను పరిగణించండి:
వెక్టర్ < int > B = { - రెండు , 1 , - 3 , 4 , - 1 , రెండు , 1 , - 5 , 4 } ;
గరిష్ట మొత్తంతో కూడిన స్లైస్ (ఉప-శ్రేణి) క్రమం, {4, −1, 2, 1} ఇది 6 మొత్తాన్ని ఇస్తుంది. గరిష్ట మొత్తానికి ఉప-శ్రేణిలో ప్రతికూల సంఖ్యలు ఉండవచ్చని గమనించండి.
కింది వెక్టర్‌ను పరిగణించండి:
వెక్టర్ < int > సి = { 3 , రెండు , - 6 , 4 , 0 } ;
గరిష్ట మొత్తంతో స్లైస్ (ఉప-శ్రేణి) క్రమం, {3, 2} ఇది 5 మొత్తాన్ని ఇస్తుంది.
కింది వెక్టర్‌ను పరిగణించండి:
వెక్టర్ < int > D = { 3 , రెండు , 6 , - 1 , 4 , 5 , - 1 , రెండు } ;
గరిష్ట మొత్తంతో కూడిన ఉప-శ్రేణి క్రమం, {3, 2, 6, -1, 4, 5, -1, 2} ఇది 20 మొత్తాన్ని ఇస్తుంది. ఇది మొత్తం శ్రేణి.
కింది వెక్టర్‌ను పరిగణించండి:
వెక్టర్ < int > E = { 5 , 7 , - 4 , - 10 , - 6 , 6 , 5 , 10 , - 5 , పదిహేను , 4 , - 8 , - పదిహేను , - 22 } ;
ఇక్కడ గరిష్ట మొత్తాలతో రెండు ఉప-శ్రేణులు ఉన్నాయి. అధిక మొత్తం అనేది గరిష్ట ఉప-శ్రేణి సమస్యకు పరిష్కారం (సమాధానం)గా పరిగణించబడుతుంది. ఉప-శ్రేణులు: 12 మొత్తంతో {5, 7} మరియు 35 మొత్తంతో {6, 5, 10, -5, 15, 4}. వాస్తవానికి, 35 మొత్తంతో స్లైస్, సమాధానం.
కింది వెక్టర్‌ను పరిగణించండి:
వెక్టర్ < int > F = { - 4 , 10 , పదిహేను , 9 , - 5 , - ఇరవై , - 3 , - 12 , - 3 , 4 , 6 , 3 , రెండు , 8 , 3 , - 5 , - రెండు } ;
గరిష్ట మొత్తాలతో రెండు ఉప-శ్రేణులు ఉన్నాయి. అధిక మొత్తం అనేది గరిష్ట ఉప-శ్రేణి సమస్యకు పరిష్కారంగా పరిగణించబడుతుంది. ఉప-శ్రేణులు: 34 మొత్తంతో {10, 15, 9} మరియు 26 మొత్తంతో {4, 6, 3, 2, 8, 3}. వాస్తవానికి, 34 మొత్తంతో స్లైస్ ఉంటుంది సమాధానం ఎందుకంటే సమస్య అత్యధిక మొత్తంతో ఉప-శ్రేణిని వెతకడం మరియు అధిక మొత్తంతో ఉప-శ్రేణిని కాదు.
కడనే యొక్క అల్గారిథమ్‌ను అభివృద్ధి చేయడం
ట్యుటోరియల్‌లోని ఈ విభాగంలోని సమాచారం కడానే నుండి వచ్చిన అసలు పని కాదు. కడనే అల్గారిథమ్‌ని బోధించడం రచయిత సొంత మార్గం. పైన పేర్కొన్న వెక్టర్‌లలో ఒకటి, దాని నడుస్తున్న మొత్తాలతో, ఈ పట్టికలో ఉంది:
| సమాచారం | 5 | 7 | -4 | -10 | -6 | 6 | 5 | 10 | -5 | పదిహేను | 4 | -8 | - పదిహేను | -22 |
| మొత్తం రన్ అవుతోంది | 5 | 12 | 8 | -రెండు | -8 | -రెండు | 3 | 13 | 8 | 23 | 27 | ఇరవై ఒకటి | 16 | -6 |
| సూచిక | 0 | 1 | రెండు | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | పదకొండు | 12 | 13 |
ఇండెక్స్ కోసం రన్ టోటల్ అనేది ఇండెక్స్‌తో సహా మునుపటి అన్ని విలువల మొత్తం. ఇక్కడ గరిష్ట మొత్తాలతో రెండు సీక్వెన్సులు ఉన్నాయి. అవి {5, 7}, ఇది 12 మొత్తాన్ని ఇస్తుంది, మరియు {6, 5, 10, -5, 15, 4}, ఇది 35 మొత్తాన్ని ఇస్తుంది. 35 మొత్తాన్ని ఇచ్చే క్రమం కోరుకున్నది .
రన్నింగ్ మొత్తాలకు, 12 మరియు 27 అనే రెండు శిఖరాలు ఉన్నాయని గమనించండి. ఈ శిఖరాలు రెండు సీక్వెన్స్‌ల చివరి సూచికలకు అనుగుణంగా ఉంటాయి.
కాబట్టి, ఇవ్వబడిన శ్రేణిలో ఎడమ నుండి కుడికి కదులుతూ, ఎదురయ్యే గరిష్ట మొత్తాలను పోల్చి చూసుకుంటూ రన్ టోటల్‌ను చేయడం అనేది కడనే యొక్క అల్గారిథమ్ యొక్క ఆలోచన.
పై నుండి మరొక వెక్టర్, దాని నడుస్తున్న మొత్తాలతో, ఈ పట్టికలో ఉంది:
గరిష్ట మొత్తాలతో రెండు సీక్వెన్సులు ఉన్నాయి. అవి {10, 15, 9}, ఇది 34 మొత్తాన్ని ఇస్తుంది; మరియు {4, 6, 3, 2, 8, 3} ఇది 26 మొత్తాన్ని ఇస్తుంది. 34 మొత్తాన్ని ఇచ్చే క్రమం, కోరుకున్నది.
నడుస్తున్న మొత్తాలకు, 30 మరియు 13 అనే రెండు శిఖరాలు ఉన్నాయని గమనించండి. ఈ శిఖరాలు రెండు సీక్వెన్స్‌ల చివరి సూచికలకు అనుగుణంగా ఉంటాయి.
మళ్లీ, కడానే యొక్క అల్గారిథమ్ యొక్క ఆలోచన ఏమిటంటే, ఇచ్చిన శ్రేణిలో ఎడమ నుండి కుడికి కదులుతూ, ఎదురయ్యే గరిష్ట మొత్తాలను పోల్చి చూసేటప్పుడు మొత్తం రన్నింగ్ చేయడం.
C++లో Kadane's Algorithm ద్వారా కోడ్
కథనంలోని ఈ విభాగంలో ఇవ్వబడిన కోడ్ కాదనే ఉపయోగించాల్సిన అవసరం లేదు. అయితే, ఇది అతని అల్గోరిథం ద్వారా. అనేక ఇతర C++ ప్రోగ్రామ్‌ల వలె ప్రోగ్రామ్ దీనితో ప్రారంభమవుతుంది:
##clude<వెక్టర్>
నేమ్‌స్పేస్ stdని ఉపయోగించడం;
ఇన్‌పుట్ మరియు అవుట్‌పుట్‌కు బాధ్యత వహించే iostream లైబ్రరీని చేర్చారు. ప్రామాణిక నేమ్‌స్పేస్ ఉపయోగించబడుతుంది.
ఇచ్చిన శ్రేణిలో ఎడమ నుండి కుడికి కదులుతున్నప్పుడు ఎదురయ్యే గరిష్ట మొత్తాలను పోల్చి చూసేటప్పుడు రన్నింగ్ టోటల్‌ను కలిగి ఉండటమే కడనే యొక్క అల్గారిథమ్ యొక్క ఆలోచన. అల్గోరిథం యొక్క ఫంక్షన్:
int maxSunArray ( వెక్టర్ < int > & ఎ ) {int N = A.పరిమాణం ( ) ;
int maxSum = A [ 0 ] ;
int runTotal = A [ 0 ] ;
కోసం ( int i = 1 ; i < N; i++ ) {
int tempRunTotal = runTotal + A [ i ] ; // A కంటే చిన్నది కావచ్చు [ i ]
ఉంటే ( ఎ [ i ] > tempRunTotal )
runTotal = A [ i ] ; // లో కేసు ఎ [ i ] నడుస్తున్న మొత్తం కంటే పెద్దది
లేకపోతే
runTotal = tempRunTotal;
ఉంటే ( రన్ టోటల్ > గరిష్ట మొత్తం ) // అన్ని గరిష్ట మొత్తాలను పోల్చడం
maxSum = మొత్తం;
}
తిరిగి maxAmount;
}
ఇచ్చిన శ్రేణి (వెక్టర్) యొక్క పరిమాణం, N నిర్ణయించబడుతుంది. వేరియబుల్, maxSum సాధ్యమయ్యే గరిష్ట మొత్తాలలో ఒకటి. శ్రేణి కనీసం ఒక గరిష్ట మొత్తాన్ని కలిగి ఉంటుంది. వేరియబుల్, రన్‌టోటల్ ప్రతి ఇండెక్స్ వద్ద నడుస్తున్న మొత్తంని సూచిస్తుంది. అవి రెండూ శ్రేణి యొక్క మొదటి విలువతో ప్రారంభించబడ్డాయి. ఈ అల్గారిథమ్‌లో, శ్రేణిలోని తదుపరి విలువ నడుస్తున్న మొత్తం కంటే ఎక్కువగా ఉంటే, ఆ తదుపరి విలువ కొత్త రన్నింగ్ టోటల్‌గా మారుతుంది.
ఒక ప్రధాన లూప్ ఉంది. ఇచ్చిన శ్రేణి యొక్క మొదటి మూలకం అయిన A[0] నుండి వేరియబుల్స్, maxSum మరియు runTotal ప్రారంభించడం వలన స్కానింగ్ 1 నుండి ప్రారంభమవుతుంది మరియు సున్నా కాదు.
ఫర్-లూప్‌లో, మొదటి స్టేట్‌మెంట్ అన్ని మునుపటి విలువల యొక్క సంచిత మొత్తానికి ప్రస్తుత విలువను జోడించడం ద్వారా తాత్కాలికంగా నడుస్తున్న మొత్తాన్ని నిర్ణయిస్తుంది.
తర్వాత, if/else నిర్మాణం ఉంది. ఇప్పటి వరకు నడుస్తున్న మొత్తం కంటే ప్రస్తుత విలువ మాత్రమే ఎక్కువగా ఉంటే, ఆ ఒక్క విలువ నడుస్తున్న మొత్తం అవుతుంది. ప్రత్యేకించి ఇచ్చిన శ్రేణిలోని అన్ని విలువలు ప్రతికూలంగా ఉంటే ఇది చాలా ఉపయోగకరంగా ఉంటుంది. ఈ సందర్భంలో, అత్యధిక ప్రతికూల విలువ మాత్రమే గరిష్ట విలువ (సమాధానం) అవుతుంది. ఇప్పటి వరకు ఉన్న తాత్కాలిక రన్నింగ్ టోటల్ కంటే ప్రస్తుత విలువ మాత్రమే ఎక్కువగా లేకుంటే, రన్నింగ్ టోటల్ మునుపటి రన్నింగ్ టోటల్‌తో పాటు ప్రస్తుత విలువ కూడా అవుతుంది, – ఇది if/else కాన్‌స్ట్రక్ట్‌లో వేరే భాగం.
ఫర్-లూప్‌లోని చివరి కోడ్ సెగ్మెంట్ మునుపటి సీక్వెన్స్ (సబ్-అరే) కోసం ఏదైనా మునుపటి గరిష్ట మొత్తం మరియు ప్రస్తుత సీక్వెన్స్ కోసం ఏదైనా ప్రస్తుత గరిష్ట మొత్తం మధ్య ఎంచుకుంటుంది. కాబట్టి అధిక విలువ ఎంపిక చేయబడింది. ఒకటి కంటే ఎక్కువ గరిష్ట ఉప-శ్రేణి మొత్తం ఉండవచ్చు. శ్రేణి ఎడమ నుండి కుడికి స్కాన్ చేయబడినందున రన్నింగ్ టోటల్ పెరుగుతుందని మరియు తగ్గుతుందని గమనించండి. ఇది ప్రతికూల విలువలను కలుసుకోవడంతో పడిపోతుంది.
చివరిగా ఎంచుకున్న గరిష్ట ఉప-శ్రేణి మొత్తం ఫర్-లూప్ తర్వాత తిరిగి ఇవ్వబడుతుంది.
Kadane యొక్క అల్గోరిథం ఫంక్షన్ కోసం తగిన C++ ప్రధాన ఫంక్షన్ కోసం కంటెంట్:
వెక్టర్ < int > A = { 5 , - 7 , 3 , 5 , - రెండు , 4 , - 1 } ; // { 3 , 5 , - రెండు , 4 } - > 10int ret1 = maxSunArray ( ఎ ) ;
కోట్ << ret1 << endl;
వెక్టర్ < int > B = { - రెండు , 1 , - 3 , 4 , - 1 , రెండు , 1 , - 5 , 4 } ; // { 4 , - 1 , రెండు , 1 } - > 6
int ret2 = maxSunArray ( బి ) ;
కోట్ << ret2 << endl;
వెక్టర్ < int > సి = { 3 , రెండు , - 6 , 4 , 0 } ; // { 3 , రెండు } - > 5
int ret3 = maxSunArray ( సి ) ;
కోట్ << ret3 << endl;
వెక్టర్ < int > D = { 3 , రెండు , 6 , - 1 , 4 , 5 , - 1 , రెండు } ; // { 3 , రెండు , 6 , - 1 , 4 , 5 , - 1 , రెండు } - > 5
int ret4 = maxSunArray ( డి ) ;
కోట్ << net4 << endl;
వెక్టర్ < int > E = { 5 , 7 , - 4 , - 10 , - 6 , 6 , 5 , 10 , - 5 , పదిహేను , 4 , - 8 , - పదిహేను , - 22 } ; // { 6 , 5 , 10 , - 5 , పదిహేను , 4 } - > 35
int ret5 = maxSunArray ( మరియు ) ;
కోట్ << ret5 << endl;
వెక్టర్ < int > F = { - 4 , 10 , పదిహేను , 9 , - 5 , - ఇరవై , - 3 , - 12 , - 3 , 4 , 6 , 3 , రెండు , 8 , 3 , - 5 , - రెండు } ; // { 10 , పదిహేను , 9 } - > 3. 4
int ret6 = maxSunArray ( ఎఫ్ ) ;
కోట్ << కుడి 6 << endl;
దానితో, అవుట్పుట్ ఇలా ఉంటుంది:
10
6
5
ఇరవై
35
3. 4
ఇక్కడ ప్రతి పంక్తి సమాధానం, ఇచ్చిన శ్రేణికి అనుగుణంగా ఉంటుంది.
ముగింపు
Kadane యొక్క అల్గోరిథం యొక్క సమయ సంక్లిష్టత O(n), ఇక్కడ n అనేది ఇచ్చిన శ్రేణిలోని మూలకాల సంఖ్య. గరిష్ట ఉప-శ్రేణి సమస్యకు ఈ సమయ సంక్లిష్టత అత్యంత వేగవంతమైనది. నెమ్మదిగా ఉండే ఇతర అల్గారిథమ్‌లు ఉన్నాయి. Kadane యొక్క అల్గారిథమ్ యొక్క ఆలోచన ఏమిటంటే, రన్నింగ్ టోటల్‌ను చేయడం, అవి ఎదురయ్యే గరిష్ట మొత్తాలను సరిపోల్చడం, ఇచ్చిన శ్రేణిలో ఎడమ నుండి కుడికి కదులుతాయి. ప్రస్తుత విలువ ఒక్కటే ఇప్పటివరకు నడుస్తున్న మొత్తం కంటే ఎక్కువగా ఉంటే, ఆ ఒక్క విలువ కొత్త రన్నింగ్ టోటల్ అవుతుంది. లేకపోతే, అందించిన శ్రేణి స్కాన్ చేయబడినట్లుగా, ఊహించిన విధంగా, కొత్త రన్నింగ్ టోటల్ మునుపటి రన్నింగ్ టోటల్ మరియు ప్రస్తుత మూలకం.
వివిధ సాధ్యమయ్యే ఉప-శ్రేణుల కోసం ఒకటి కంటే ఎక్కువ గరిష్ట మొత్తం ఉండవచ్చు. సాధ్యమయ్యే అన్ని ఉప-శ్రేణుల కోసం అత్యధిక గరిష్ట మొత్తం ఎంపిక చేయబడింది.
ఎంచుకున్న గరిష్ట మొత్తం పరిధికి పరిమితి సూచికలు ఏమిటి? – అది మరికొంత కాలం చర్చ!
క్రిస్