সর্বোচ্চ সাব-অ্যারে সমস্যা ম্যাক্সিমাম স্লাইস সমস্যার মতোই। এই টিউটোরিয়ালটি C++ এ কোডিং এর সমস্যা নিয়ে আলোচনা করে। প্রশ্ন হল: একটি অ্যারের মধ্যে ক্রমিক সংখ্যাগুলির সম্ভাব্য ক্রমগুলির সর্বাধিক যোগফল কত? এই পুরো অ্যারে মানে হতে পারে. এই সমস্যাটি এবং যেকোনো ভাষায় এর সমাধানকে সর্বোচ্চ সাব-অ্যারে সমস্যা বলা হয়। অ্যারের সম্ভাব্য ঋণাত্মক সংখ্যা থাকতে পারে।
সমাধান দক্ষ হতে হবে। এটি দ্রুততম সময়ের জটিলতা থাকা প্রয়োজন। এখন পর্যন্ত, সমাধানের জন্য দ্রুততম অ্যালগরিদমটি বৈজ্ঞানিক সম্প্রদায়ে কাদানের অ্যালগরিদম নামে পরিচিত। এই নিবন্ধটি C++ এর সাথে কাদানের অ্যালগরিদম ব্যাখ্যা করে।
ডেটা উদাহরণ
নিম্নলিখিত ভেক্টর (অ্যারে) বিবেচনা করুন:
ভেক্টর < int > ক = { 5 , - 7 , 3 , 5 , - দুই , 4 , - 1 } ;
সর্বাধিক যোগফল সহ স্লাইস (সাব-অ্যারে) হল ক্রম, {3, 5, -2, 4}, যা 10 এর যোগফল দেয়। অন্য কোন সম্ভাব্য ক্রম, এমনকি পুরো অ্যারে পর্যন্ত একটি যোগফল দেবে না 10 এর মান। পুরো অ্যারেটি 7 এর যোগফল দেয়, যা সর্বোচ্চ যোগফল নয়।
নিম্নলিখিত ভেক্টর বিবেচনা করুন:
ভেক্টর < int > খ = { - দুই , 1 , - 3 , 4 , - 1 , দুই , 1 , - 5 , 4 } ;
সর্বোচ্চ যোগফল সহ স্লাইস (সাব-অ্যারে) হল ক্রম, {4, −1, 2, 1} যা 6 এর যোগফল দেয়। উল্লেখ্য যে সর্বাধিক যোগফলের জন্য সাব-অ্যারের মধ্যে ঋণাত্মক সংখ্যা থাকতে পারে।
নিম্নলিখিত ভেক্টর বিবেচনা করুন:
ভেক্টর < int > গ = { 3 , দুই , - 6 , 4 , 0 } ;
সর্বোচ্চ যোগফল সহ স্লাইস (সাব-অ্যারে) হল ক্রম, {3, 2} যা 5 এর যোগফল দেয়।
নিম্নলিখিত ভেক্টর বিবেচনা করুন:
ভেক্টর < int > ডি = { 3 , দুই , 6 , - 1 , 4 , 5 , - 1 , দুই } ;
সর্বাধিক যোগফল সহ সাব-অ্যারে হল ক্রম, {3, 2, 6, -1, 4, 5, -1, 2} যা 20 এর যোগফল দেয়। এটি পুরো অ্যারে।
নিম্নলিখিত ভেক্টর বিবেচনা করুন:
ভেক্টর < int > ই = { 5 , 7 , - 4 , - 10 , - 6 , 6 , 5 , 10 , - 5 , পনের , 4 , - 8 , - পনের , - 22 } ;
এখানে সর্বাধিক যোগফল সহ দুটি উপ-অ্যারে রয়েছে। সর্বোচ্চ সাব-অ্যারে সমস্যার জন্য সমাধান (উত্তর) হিসাবে বিবেচিত যেটি উচ্চতর সমষ্টি। সাব-অ্যারেগুলি হল: 12 এর যোগফল সহ {5, 7} এবং 35 এর যোগফল সহ {6, 5, 10, -5, 15, 4}। অবশ্যই, 35 এর যোগফল সহ স্লাইস হল উত্তর.
নিম্নলিখিত ভেক্টর বিবেচনা করুন:
ভেক্টর < int > চ = { - 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 এর যোগফল দেয়। .
লক্ষ্য করুন যে চলমান মোটের জন্য, দুটি শিখর রয়েছে যার মান হল 12 এবং 27৷ এই শিখরগুলি দুটি অনুক্রমের শেষ সূচির সাথে মিলে যায়৷
সুতরাং, Kadane-এর অ্যালগরিদমের ধারণা হল প্রদত্ত অ্যারেতে বাম থেকে ডানে সরে গিয়ে সর্বাধিক যোগফলের তুলনা করার সময় রানিং টোটাল করা।
উপরে থেকে আরেকটি ভেক্টর, তার চলমান মোট সহ, এই টেবিলে রয়েছে:
সর্বাধিক যোগফল সহ দুটি ক্রম রয়েছে। তারা হল {10, 15, 9}, যা 34 এর যোগফল দেয়; এবং {4, 6, 3, 2, 8, 3} যা 26 এর যোগফল দেয়। যে ক্রমটি 34 এর যোগফল দেয়, সেটিই কাঙ্ক্ষিত।
লক্ষ্য করুন যে চলমান মোটের জন্য, দুটি শিখর রয়েছে যার মান হল 30 এবং 13৷ এই শিখরগুলি দুটি অনুক্রমের শেষ সূচির সাথে মিলে যায়৷
আবার, Kadane-এর অ্যালগরিদমের ধারণা হল, প্রদত্ত অ্যারেতে বাম থেকে ডানে সরে গিয়ে সর্বাধিক যোগফলের তুলনা করার সময় চলমান মোট করা।
C++ এ কাদানের অ্যালগরিদমের কোড
নিবন্ধের এই বিভাগে প্রদত্ত কোডটি কাদানে ব্যবহার করা আবশ্যক নয়। যাইহোক, এটি তার অ্যালগরিদম দ্বারা হয়. অন্যান্য অনেক C++ প্রোগ্রামের মতো প্রোগ্রামটি শুরু হবে:
# অন্তর্ভুক্ত করুন# অন্তর্ভুক্ত <ভেক্টর>
নামস্থান std ব্যবহার করে;
আইওস্ট্রিম লাইব্রেরির অন্তর্ভুক্তি রয়েছে, যা ইনপুট এবং আউটপুটের জন্য দায়ী। স্ট্যান্ডার্ড নেমস্পেস ব্যবহার করা হয়।
Kadane-এর অ্যালগরিদমের ধারণা হল, প্রদত্ত অ্যারেতে বাম থেকে ডানে সরে গিয়ে সর্বাধিক যোগফলের তুলনা করার সময় চলমান মোট থাকা। অ্যালগরিদমের ফাংশন হল:
int maxSunArray ( ভেক্টর < int > এবং ক ) {int N = A.size ( ) ;
int maxSum = A [ 0 ] ;
int runTotal = A [ 0 ] ;
জন্য ( int i = 1 ; i < এন; i++ ) {
int tempRunTotal = runTotal + A [ i ] ; // A এর চেয়ে ছোট হতে পারে [ i ]
যদি ( ক [ i ] > tempRunTotal )
runTotal = A [ i ] ; // ভিতরে মামলা ক [ i ] চলমান মোটের চেয়ে বড়
অন্য
runTotal = tempRunTotal;
যদি ( রান টোটাল > সর্বোচ্চ পরিমাণ ) // সব সর্বোচ্চ রাশি তুলনা
maxSum = runTotal;
}
প্রত্যাবর্তন সর্বাধিক পরিমাণ;
}
প্রদত্ত অ্যারের (ভেক্টর) আকার, N নির্ধারণ করা হয়। পরিবর্তনশীল, maxSum হল সম্ভাব্য সর্বোচ্চ রাশিগুলির মধ্যে একটি। একটি অ্যারের অন্তত একটি সর্বোচ্চ যোগফল আছে। ভেরিয়েবল, রানটোটাল প্রতিটি সূচকে চলমান মোটের প্রতিনিধিত্ব করে। তারা উভয় অ্যারের প্রথম মান সঙ্গে আরম্ভ করা হয়. এই অ্যালগরিদমে, অ্যারের পরবর্তী মানটি চলমান মোটের চেয়ে বেশি হলে পরবর্তী মানটি নতুন চলমান মোটে পরিণত হবে।
একটি প্রধান জন্য লুপ আছে. ভেরিয়েবল, maxSum এবং runTotal থেকে A[0] যা প্রদত্ত অ্যারের প্রথম উপাদানের প্রাথমিককরণের কারণে স্ক্যানিং 1 থেকে শুরু হয় এবং শূন্য নয়।
ফর-লুপে, প্রথম বিবৃতিটি পূর্ববর্তী সমস্ত মানের সঞ্চিত যোগফলের সাথে বর্তমান মান যোগ করে একটি অস্থায়ী চলমান মোট নির্ধারণ করে।
পরবর্তী, একটি if/else নির্মাণ আছে। যদি বর্তমান মানটি এখন পর্যন্ত চলমান মোটের চেয়ে বেশি হয়, তাহলে সেই একক মানটি চলমান মোটে পরিণত হয়। এটি সুবিধাজনক বিশেষ করে যদি প্রদত্ত অ্যারের সমস্ত মান ঋণাত্মক হয়। এই ক্ষেত্রে, একা সর্বোচ্চ ঋণাত্মক মান সর্বাধিক মান (উত্তর) হয়ে যাবে। যদি বর্তমান মানটি এখন পর্যন্ত অস্থায়ী চলমান মোটের চেয়ে বেশি না হয়, তাহলে চলমান মোট পূর্ববর্তী চলমান মোট এবং বর্তমান মান হয়ে যায়, - এটি if/else গঠনের অন্য অংশ।
ফর-লুপের শেষ কোড সেগমেন্টটি পূর্ববর্তী সিকোয়েন্সের (সাব-অ্যারে) জন্য যেকোনো পূর্ববর্তী সর্বোচ্চ যোগফল এবং বর্তমান ক্রমটির জন্য যেকোনো বর্তমান সর্বাধিক যোগফলের মধ্যে বেছে নেয়। উচ্চ মান তাই নির্বাচিত হয়. সর্বোচ্চ একাধিক সাব-অ্যারে যোগফল থাকতে পারে। লক্ষ্য করুন যে রানিং টোটাল বাড়বে এবং পড়ে যাবে, কারণ অ্যারেটি বাম থেকে ডানে স্ক্যান করা হয়। এটি নেতিবাচক মান পূরণের সাথে সাথে পড়ে।
চূড়ান্ত নির্বাচিত সর্বোচ্চ সাব-অ্যারে যোগফল ফর-লুপের পরে ফেরত দেওয়া হয়।
কাদানের অ্যালগরিদম ফাংশনের জন্য উপযুক্ত C++ প্রধান ফাংশনের বিষয়বস্তু হল:
ভেক্টর < int > ক = { 5 , - 7 , 3 , 5 , - দুই , 4 , - 1 } ; // { 3 , 5 , - দুই , 4 } - > 10int ret1 = maxSunArray ( ক ) ;
cout << ret1 << endl;
ভেক্টর < int > খ = { - দুই , 1 , - 3 , 4 , - 1 , দুই , 1 , - 5 , 4 } ; // { 4 , - 1 , দুই , 1 } - > 6
int ret2 = maxSunArray ( খ ) ;
cout << ret2 << endl;
ভেক্টর < int > গ = { 3 , দুই , - 6 , 4 , 0 } ; // { 3 , দুই } - > 5
int ret3 = maxSunArray ( গ ) ;
cout << ret3 << endl;
ভেক্টর < int > ডি = { 3 , দুই , 6 , - 1 , 4 , 5 , - 1 , দুই } ; // { 3 , দুই , 6 , - 1 , 4 , 5 , - 1 , দুই } - > 5
int ret4 = maxSunArray ( ডি ) ;
cout << net4 << endl;
ভেক্টর < int > ই = { 5 , 7 , - 4 , - 10 , - 6 , 6 , 5 , 10 , - 5 , পনের , 4 , - 8 , - পনের , - 22 } ; // { 6 , 5 , 10 , - 5 , পনের , 4 } - > 35
int ret5 = maxSunArray ( এবং ) ;
cout << ret5 << endl;
ভেক্টর < int > চ = { - 4 , 10 , পনের , 9 , - 5 , - বিশ , - 3 , - 12 , - 3 , 4 , 6 , 3 , দুই , 8 , 3 , - 5 , - দুই } ; // { 10 , পনের , 9 } - > 3. 4
int ret6 = maxSunArray ( চ ) ;
cout << ডান 6 << endl;
এর সাথে, আউটপুট হবে:
10
6
5
বিশ
35
3. 4
এখানে প্রতিটি লাইন উত্তর, একটি প্রদত্ত অ্যারের সাথে সঙ্গতিপূর্ণ, ক্রমানুসারে।
উপসংহার
কাদানের অ্যালগরিদমের সময় জটিলতা হল O(n), যেখানে n হল প্রদত্ত অ্যারের উপাদানগুলির সংখ্যা। এই সময়ের জটিলতা সর্বাধিক সাব-অ্যারে সমস্যার জন্য দ্রুততম। অন্যান্য অ্যালগরিদম রয়েছে যা ধীর। Kadane-এর অ্যালগরিদমের ধারণা হল চলমান মোট করা, প্রদত্ত অ্যারেতে বাম থেকে ডানে সরে যাওয়া সর্বাধিক যোগফলের তুলনা করা। যদি বর্তমান মান এখন পর্যন্ত চলমান মোটের চেয়ে বেশি হয়, তাহলে সেই একক মানটি নতুন চলমান মোটে পরিণত হবে। অন্যথায়, নতুন চলমান মোট পূর্ববর্তী চলমান মোট এবং বর্তমান উপাদান, যেমন প্রত্যাশিত অ্যারে স্ক্যান করা হয়েছে।
বিভিন্ন সম্ভাব্য সাব-অ্যারের জন্য একাধিক সর্বোচ্চ যোগফল থাকতে পারে। সম্ভাব্য সব সাব-অ্যারের জন্য সর্বোচ্চ সর্বোচ্চ যোগফল বেছে নেওয়া হয়েছে।
নির্বাচিত সর্বোচ্চ যোগফলের পরিসরের জন্য সীমাবদ্ধ সূচকগুলি কী কী? - এটা অন্য সময়ের জন্য আলোচনা!
ক্রিস