அதிகபட்ச சப்-அரே பிரச்சனை என்பது அதிகபட்ச ஸ்லைஸ் பிரச்சனைக்கு சமம். இந்த டுடோரியல் C++ இல் குறியீட்டில் உள்ள சிக்கலைப் பற்றி விவாதிக்கிறது. கேள்வி: ஒரு வரிசையில் உள்ள தொடர்ச்சியான எண்களின் சாத்தியமான வரிசையின் அதிகபட்ச தொகை என்ன? இது முழு வரிசையையும் குறிக்கலாம். எந்த மொழியிலும் இந்தப் பிரச்சனையும் அதற்கான தீர்வும், அதிகபட்ச துணை-வரிசைப் பிரச்சனை என்று குறிப்பிடப்படுகிறது. வரிசை சாத்தியமான எதிர்மறை எண்களைக் கொண்டிருக்கலாம்.
தீர்வு திறமையாக இருக்க வேண்டும். இது வேகமான நேர சிக்கலைக் கொண்டிருக்க வேண்டும். தற்போதைய நிலவரப்படி, தீர்வுக்கான அதிவேக வழிமுறையானது அறிவியல் சமூகத்தில் கடனின் அல்காரிதம் என அறியப்படுகிறது. இந்தக் கட்டுரை C++ உடன் கடனேயின் வழிமுறையை விளக்குகிறது.
தரவு எடுத்துக்காட்டுகள்
பின்வரும் வெக்டரை (வரிசை) கவனியுங்கள்:
திசையன் < முழு எண்ணாக > ஏ = { 5 , - 7 , 3 , 5 , - இரண்டு , 4 , - 1 } ;
அதிகபட்சத் தொகையுடன் கூடிய ஸ்லைஸ் (துணை அணி) வரிசை, {3, 5, -2, 4}, இது 10ஐக் கொடுக்கும். வேறு எந்த சாத்தியமான வரிசையும், முழு வரிசையும் கூட, இது வரையிலான தொகையைக் கொடுக்காது. 10 இன் மதிப்பு. முழு அணிவரிசையும் 7 இன் கூட்டுத்தொகையை அளிக்கிறது, இது அதிகபட்ச தொகை அல்ல.
பின்வரும் வெக்டரைக் கவனியுங்கள்:
திசையன் < முழு எண்ணாக > பி = { - இரண்டு , 1 , - 3 , 4 , - 1 , இரண்டு , 1 , - 5 , 4 } ;
அதிகபட்சத் தொகையுடன் கூடிய ஸ்லைஸ் (துணை அணி) வரிசை, {4, −1, 2, 1} இது 6 இன் கூட்டுத்தொகையைக் கொடுக்கும். அதிகபட்சத் தொகைக்கு துணை அணிக்குள் எதிர்மறை எண்கள் இருக்கலாம் என்பதை நினைவில் கொள்ளவும்.
பின்வரும் வெக்டரைக் கவனியுங்கள்:
திசையன் < முழு எண்ணாக > சி = { 3 , இரண்டு , - 6 , 4 , 0 } ;
அதிகபட்ச கூட்டுத்தொகை கொண்ட ஸ்லைஸ் (துணை வரிசை) வரிசை, {3, 2}, இது 5ஐக் கொடுக்கும்.
பின்வரும் வெக்டரைக் கவனியுங்கள்:
திசையன் < முழு எண்ணாக > D = { 3 , இரண்டு , 6 , - 1 , 4 , 5 , - 1 , இரண்டு } ;
அதிகபட்ச கூட்டுத்தொகை கொண்ட துணை அணிவரிசை வரிசை, {3, 2, 6, -1, 4, 5, -1, 2} இது 20ஐக் கொடுக்கும். இது முழு அணிவரிசையாகும்.
பின்வரும் வெக்டரைக் கவனியுங்கள்:
திசையன் < முழு எண்ணாக > ஈ = { 5 , 7 , - 4 , - 10 , - 6 , 6 , 5 , 10 , - 5 , பதினைந்து , 4 , - 8 , - பதினைந்து , - 22 } ;
இங்கு அதிகபட்ச தொகைகளுடன் இரண்டு துணை அணிவரிசைகள் உள்ளன. அதிக தொகை என்பது அதிகபட்ச துணை அணி சிக்கலுக்கான தீர்வாக (பதில்) கருதப்படுகிறது. துணை வரிசைகள்: {5, 7} 12 தொகையுடன், மற்றும் {6, 5, 10, -5, 15, 4} 35 இன் கூட்டுத்தொகையுடன். நிச்சயமாக, 35 இன் கூட்டுத்தொகை கொண்ட ஸ்லைஸ், பதில்.
பின்வரும் வெக்டரைக் கவனியுங்கள்:
திசையன் < முழு எண்ணாக > எஃப் = { - 4 , 10 , பதினைந்து , 9 , - 5 , - இருபது , - 3 , - 12 , - 3 , 4 , 6 , 3 , இரண்டு , 8 , 3 , - 5 , - இரண்டு } ;
அதிகபட்ச தொகைகளுடன் இரண்டு துணை அணிகள் உள்ளன. அதிகத் தொகையே அதிகபட்ச துணை வரிசைப் பிரச்சனைக்கான தீர்வாகக் கருதப்படுகிறது. துணை அணிவரிசைகள்: {10, 15, 9} 34 கூட்டுத்தொகையுடன், மற்றும் {4, 6, 3, 2, 8, 3} 26 கூட்டுத்தொகையுடன். நிச்சயமாக, 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 ஐக் கொடுக்கும். .
இயங்கும் மொத்தங்களுக்கு, 12 மற்றும் 27 ஆகிய இரண்டு உச்சநிலைகள் உள்ளன என்பதைக் கவனியுங்கள். இந்த உச்சநிலைகள் இரண்டு வரிசைகளின் கடைசி குறியீடுகளுடன் ஒத்துப்போகின்றன.
எனவே, கடனேவின் வழிமுறையின் யோசனை என்னவென்றால், கொடுக்கப்பட்ட வரிசையில் இடமிருந்து வலமாக நகர்ந்து, எதிர்கொள்ளும் அதிகபட்ச தொகைகளை ஒப்பிடும் போது, இயங்கும் மொத்தத்தை செய்வதாகும்.
மேலே இருந்து மற்றொரு திசையன், அதன் இயங்கும் மொத்தங்கள், இந்த அட்டவணையில் உள்ளது:
அதிகபட்ச தொகைகளுடன் இரண்டு வரிசைகள் உள்ளன. அவை {10, 15, 9}, இது 34ஐக் கொடுக்கும்; மற்றும் {4, 6, 3, 2, 8, 3} என்பது 26ஐத் தரும்.
இயங்கும் மொத்தங்களுக்கு, 30 மற்றும் 13 ஆகிய இரண்டு உச்சநிலைகள் உள்ளன என்பதை கவனியுங்கள்.
மீண்டும், கடனேவின் வழிமுறையின் யோசனை என்னவென்றால், கொடுக்கப்பட்ட வரிசையில் இடமிருந்து வலமாக நகர்ந்து, எதிர்கொள்ளும் அதிகபட்ச தொகைகளை ஒப்பிடும் போது, இயங்கும் மொத்தத்தை செய்வதாகும்.
C++ இல் கடனேயின் அல்காரிதம் மூலம் குறியீடு
கட்டுரையின் இந்தப் பகுதியில் கொடுக்கப்பட்டுள்ள குறியீடு கடனே பயன்படுத்தியதாக இருக்க வேண்டிய அவசியமில்லை. இருப்பினும், இது அவரது வழிமுறையால். மற்ற பல C++ நிரல்களைப் போலவே நிரலும் தொடங்கும்:
##அடங்கும்<வெக்டார்>
பெயர்வெளி std ஐப் பயன்படுத்துதல்;
உள்ளீடு மற்றும் வெளியீட்டிற்கு பொறுப்பான iostream நூலகம் சேர்க்கப்பட்டுள்ளது. நிலையான பெயர்வெளி பயன்படுத்தப்படுகிறது.
கொடுக்கப்பட்ட வரிசையில் இடமிருந்து வலமாக நகர்ந்து, எதிர்ப்படும் அதிகபட்ச தொகைகளை ஒப்பிடும் போது, இயங்கும் மொத்தத்தை கொண்டிருப்பதே கடனேயின் வழிமுறையின் கருத்து. அல்காரிதத்திற்கான செயல்பாடு:
int maxSunArray ( திசையன் < முழு எண்ணாக > & ஏ ) {int N = A. அளவு ( ) ;
int maxSum = A [ 0 ] ;
int runTotal = A [ 0 ] ;
க்கான ( முழு எண்ணாக நான் = 1 ; நான் < N; நான்++ ) {
int tempRunTotal = runTotal + A [ நான் ] ; // A விட சிறியதாக இருக்கலாம் [ நான் ]
என்றால் ( ஏ [ நான் ] > tempRunTotal )
ரன்டோட்டல் = ஏ [ நான் ] ; // உள்ளே வழக்கு ஏ [ நான் ] இயங்கும் மொத்தத்தை விட பெரியது
வேறு
runTotal = tempRunTotal;
என்றால் ( ரன் டோட்டல் > அதிகபட்ச தொகை ) // அனைத்து அதிகபட்ச தொகைகளையும் ஒப்பிடுகிறது
maxSum = runTotal;
}
திரும்ப அதிகபட்ச தொகை;
}
கொடுக்கப்பட்ட வரிசையின் (திசையன்) அளவு, N தீர்மானிக்கப்படுகிறது. மாறி, maxSum சாத்தியமான அதிகபட்ச தொகைகளில் ஒன்றாகும். ஒரு அணிவரிசையில் குறைந்தபட்சம் ஒரு அதிகபட்ச தொகை இருக்கும். மாறி, runTotal ஒவ்வொரு குறியீட்டிலும் இயங்கும் மொத்தத்தைக் குறிக்கிறது. அவை இரண்டும் வரிசையின் முதல் மதிப்புடன் துவக்கப்படும். இந்த அல்காரிதத்தில், வரிசையில் அடுத்த மதிப்பு இயங்கும் மொத்தத்தை விட அதிகமாக இருந்தால், அந்த அடுத்த மதிப்பு புதிய இயங்கும் மொத்தமாக மாறும்.
ஒரு முக்கிய ஃபார்-லூப் உள்ளது. ஸ்கேனிங் 1 இலிருந்து தொடங்குகிறது மற்றும் பூஜ்ஜியமாக இல்லாமல் மாறிகள், maxSum மற்றும் runTotal ஆகியவை A[0] க்கு கொடுக்கப்பட்ட வரிசையின் முதல் உறுப்பு ஆகும்.
ஃபார்-லூப்பில், முதல் அறிக்கையானது முந்தைய அனைத்து மதிப்புகளின் திரட்டப்பட்ட தொகையுடன் தற்போதைய மதிப்பைச் சேர்ப்பதன் மூலம் தற்காலிகமாக இயங்கும் மொத்தத்தை தீர்மானிக்கிறது.
அடுத்து, if/else கன்ஸ்ட்ரக்ட் உள்ளது. தற்போதைய மதிப்பு மட்டும் இதுவரை இயங்கும் மொத்தத்தை விட அதிகமாக இருந்தால், அந்த ஒற்றை மதிப்பு இயங்கும் மொத்தமாக மாறும். குறிப்பாக கொடுக்கப்பட்ட அணிவரிசையில் உள்ள அனைத்து மதிப்புகளும் எதிர்மறையாக இருந்தால் இது எளிது. இந்த வழக்கில், அதிக எதிர்மறை மதிப்பு மட்டுமே அதிகபட்ச மதிப்பாக மாறும் (பதில்). தற்போதைய மதிப்பு மட்டும் இதுவரை தற்காலிகமாக இயங்கும் மொத்தத்தை விட அதிகமாக இல்லை என்றால், இயங்கும் மொத்தமானது முந்தைய இயங்கும் மொத்தமும் தற்போதைய மதிப்பும் ஆகும், - இது if/else கட்டமைப்பின் மற்ற பகுதி.
ஃபார்-லூப்பில் உள்ள கடைசி குறியீட்டுப் பிரிவு, முந்தைய வரிசைக்கான (துணை-வரிசை) முந்தைய அதிகபட்சத் தொகைக்கும் தற்போதைய வரிசைக்கான தற்போதைய அதிகபட்சத் தொகைக்கும் இடையே தேர்வு செய்யும். எனவே அதிக மதிப்பு தேர்ந்தெடுக்கப்பட்டது. ஒன்றுக்கு மேற்பட்ட அதிகபட்ச துணை அணித் தொகை இருக்கலாம். வரிசை இடமிருந்து வலமாக ஸ்கேன் செய்யப்படுவதால், இயங்கும் மொத்தமானது உயரும் மற்றும் குறையும் என்பதை நினைவில் கொள்ளவும். எதிர்மறை மதிப்புகளை சந்திக்கும் போது அது விழுகிறது.
இறுதியாகத் தேர்ந்தெடுக்கப்பட்ட அதிகபட்ச துணை-வரிசைத் தொகை ஃபார்-லூப்பிற்குப் பிறகு வழங்கப்படும்.
Kadane இன் அல்காரிதம் செயல்பாட்டிற்கான பொருத்தமான C++ முக்கிய செயல்பாட்டிற்கான உள்ளடக்கம்:
திசையன் < முழு எண்ணாக > ஏ = { 5 , - 7 , 3 , 5 , - இரண்டு , 4 , - 1 } ; // { 3 , 5 , - இரண்டு , 4 } - > 10int ret1 = maxSunArray ( ஏ ) ;
கூட் << ret1 << endl;
திசையன் < முழு எண்ணாக > பி = { - இரண்டு , 1 , - 3 , 4 , - 1 , இரண்டு , 1 , - 5 , 4 } ; // { 4 , - 1 , இரண்டு , 1 } - > 6
int ret2 = maxSunArray ( பி ) ;
கூட் << ret2 << endl;
திசையன் < முழு எண்ணாக > சி = { 3 , இரண்டு , - 6 , 4 , 0 } ; // { 3 , இரண்டு } - > 5
int ret3 = maxSunArray ( சி ) ;
கூட் << ret3 << endl;
திசையன் < முழு எண்ணாக > D = { 3 , இரண்டு , 6 , - 1 , 4 , 5 , - 1 , இரண்டு } ; // { 3 , இரண்டு , 6 , - 1 , 4 , 5 , - 1 , இரண்டு } - > 5
int ret4 = maxSunArray ( டி ) ;
கூட் << net4 << endl;
திசையன் < முழு எண்ணாக > ஈ = { 5 , 7 , - 4 , - 10 , - 6 , 6 , 5 , 10 , - 5 , பதினைந்து , 4 , - 8 , - பதினைந்து , - 22 } ; // { 6 , 5 , 10 , - 5 , பதினைந்து , 4 } - > 35
int ret5 = maxSunArray ( மற்றும் ) ;
கூட் << ret5 << endl;
திசையன் < முழு எண்ணாக > எஃப் = { - 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
இங்குள்ள ஒவ்வொரு வரிப் பதிலும், கொடுக்கப்பட்ட வரிசைக்கு வரிசையாக ஒத்திருக்கும்.
முடிவுரை
கடனேயின் அல்காரிதத்திற்கான நேர சிக்கலானது O(n), இங்கு n என்பது கொடுக்கப்பட்ட வரிசையில் உள்ள உறுப்புகளின் எண்ணிக்கை. இந்த நேர சிக்கலானது அதிகபட்ச துணை-வரிசை சிக்கலுக்கு வேகமானது. மெதுவான மற்ற அல்காரிதம்களும் உள்ளன. கொடுக்கப்பட்ட வரிசையில் இடமிருந்து வலமாக நகர்ந்து, எதிர்ப்படும் அதிகபட்ச தொகைகளை ஒப்பிடும் போது, இயங்கும் மொத்தத்தை செய்வதே கடனேவின் வழிமுறையின் கருத்து. தற்போதைய மதிப்பு மட்டும் இதுவரை இயங்கும் மொத்தத்தை விட அதிகமாக இருந்தால், அந்த ஒற்றை மதிப்பு புதிய இயங்கும் மொத்தமாக மாறும். இல்லையெனில், புதிய இயங்கும் மொத்தமானது, கொடுக்கப்பட்ட வரிசை ஸ்கேன் செய்யப்படும்போது, எதிர்பார்த்தபடி, முந்தைய இயங்கும் மொத்தமும் தற்போதைய உறுப்பும் ஆகும்.
வெவ்வேறு சாத்தியமான துணை அணிகளுக்கு ஒன்றுக்கு மேற்பட்ட அதிகபட்ச தொகைகள் இருக்கலாம். சாத்தியமான அனைத்து துணை அணிகளுக்கும் அதிகபட்ச அதிகபட்ச தொகை தேர்ந்தெடுக்கப்பட்டது.
தேர்ந்தெடுக்கப்பட்ட அதிகபட்ச தொகையின் வரம்பிற்கான வரம்புக்குட்பட்ட குறியீடுகள் என்ன? – அது வேறு சில நேரம் விவாதம்!
கிறிஸ்