زیادہ سے زیادہ ذیلی صف کا مسئلہ وہی ہے جو زیادہ سے زیادہ سلائس کا مسئلہ ہے۔ یہ ٹیوٹوریل C++ میں کوڈنگ کے مسئلے پر بحث کرتا ہے۔ سوال یہ ہے کہ: ایک صف میں لگاتار نمبروں کی کسی بھی ممکنہ ترتیب کا زیادہ سے زیادہ مجموعہ کیا ہے؟ اس کا مطلب پوری صف ہو سکتی ہے۔ یہ مسئلہ اور کسی بھی زبان میں اس کا حل، Maximum Sub-Array Problem کہلاتا ہے۔ صف میں ممکنہ منفی نمبر ہو سکتے ہیں۔
حل کارآمد ہونا چاہیے۔ اسے تیز ترین وقت کی پیچیدگی کی ضرورت ہے۔ ابھی تک، حل کے لیے تیز ترین الگورتھم کو سائنسی برادری میں Kadane’s Algorithm کے نام سے جانا جاتا ہے۔ یہ مضمون C++ کے ساتھ Kadane کے الگورتھم کی وضاحت کرتا ہے۔
ڈیٹا کی مثالیں۔
درج ذیل ویکٹر (سرنی) پر غور کریں:
ویکٹر < 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 } ;
یہاں زیادہ سے زیادہ رقم کے ساتھ دو ذیلی صفیں ہیں۔ زیادہ رقم وہ ہے جسے زیادہ سے زیادہ ذیلی صف کے مسئلے کا حل (جواب) سمجھا جاتا ہے۔ ذیلی صفیں ہیں: {5، 7} 12 کے مجموعہ کے ساتھ، اور {6، 5، 10، -5، 15، 4} 35 کے مجموعہ کے ساتھ۔ یقیناً، 35 کے مجموعہ کے ساتھ سلائس، ہے جواب.
مندرجہ ذیل ویکٹر پر غور کریں:
ویکٹر < int > F = { - 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 کے مجموعہ کے ساتھ سلائس ہے جواب کیونکہ مسئلہ سب سے زیادہ رقم کے ساتھ ذیلی صف کو تلاش کرنے کا ہے نہ کہ زیادہ رقم کے ساتھ ذیلی صف کو تلاش کرنا۔
Kadane کا الگورتھم تیار کرنا
ٹیوٹوریل کے اس حصے میں دی گئی معلومات کاڈانے کا اصل کام نہیں ہے۔ Kadane کے الگورتھم کو سکھانے کا یہ مصنف کا اپنا طریقہ ہے۔ مندرجہ بالا ویکٹر میں سے ایک، اس کے چلنے والے ٹوٹل کے ساتھ، اس جدول میں ہے:
| ڈیٹا | 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۔ یہ چوٹیاں دو ترتیبوں کے آخری اشاریہ سے مطابقت رکھتی ہیں۔
لہٰذا، Kadane کے الگورتھم کا خیال یہ ہے کہ زیادہ سے زیادہ رقموں کا آپس میں موازنہ کرتے ہوئے، دی گئی صف میں بائیں سے دائیں حرکت کرتے ہوئے رننگ کل کرنا ہے۔
اوپر سے ایک اور ویکٹر، اس کے چلنے والے ٹوٹل کے ساتھ، اس جدول میں ہے:
زیادہ سے زیادہ رقم کے ساتھ دو سلسلے ہیں۔ وہ ہیں {10، 15، 9}، جو 34 کا مجموعہ دیتا ہے؛ اور {4، 6، 3، 2، 8، 3} جو 26 کا مجموعہ دیتا ہے۔ جو ترتیب 34 کا مجموعہ دیتا ہے، وہ مطلوبہ ہے۔
دھیان دیں کہ چلنے والے ٹوٹل کے لیے، دو چوٹیاں ہیں جو کہ قدریں ہیں، 30 اور 13۔ یہ چوٹیاں دو ترتیبوں کے آخری اشاریہ سے مطابقت رکھتی ہیں۔
ایک بار پھر، Kadane کے الگورتھم کا خیال یہ ہے کہ رننگ کل کو انجام دیا جائے جبکہ زیادہ سے زیادہ رقموں کا آپس میں موازنہ کرتے ہوئے، دی گئی صف میں بائیں سے دائیں حرکت کرتے ہوئے۔
C++ میں Kadane کے الگورتھم کے ذریعے کوڈ
مضمون کے اس حصے میں جو کوڈ دیا گیا ہے وہ ضروری نہیں ہے کہ کڈانے استعمال کیا ہو۔ تاہم، یہ اس کے الگورتھم کی طرف سے ہے. یہ پروگرام بہت سے دوسرے C++ پروگراموں کی طرح شروع ہوگا:
# شامل کریں#شامل <ویکٹر>
نام کی جگہ کا استعمال کرتے ہوئے std؛
iostream لائبریری کی شمولیت ہے، جو ان پٹ اور آؤٹ پٹ کے لیے ذمہ دار ہے۔ معیاری نام کی جگہ استعمال کی جاتی ہے۔
کڈانے کے الگورتھم کا خیال یہ ہے کہ زیادہ سے زیادہ رقموں کا موازنہ کرتے ہوئے چل رہا ہے جو کہ ان کا سامنا ہے، دی گئی صف میں بائیں سے دائیں منتقل ہونا۔ الگورتھم کا فنکشن یہ ہے:
int maxSunArray ( ویکٹر < int > اور اے ) {int N = A.size ( ) ;
int maxSum = A [ 0 ] ;
int runTotal = A [ 0 ] ;
کے لیے ( int میں = 1 ; میں < ن; i++ ) {
int tempRunTotal = runTotal + A [ میں ] ; // A سے چھوٹا ہو سکتا ہے۔ [ میں ]
اگر ( اے [ میں ] > tempRunTotal )
runTotal = A [ میں ] ; // میں معاملہ اے [ میں ] چلنے والے کل سے بڑا ہے۔
اور
runTotal = tempRunTotal؛
اگر ( رن ٹوٹل > زیادہ سے زیادہ رقم ) // تمام زیادہ سے زیادہ رقوم کا موازنہ کرنا
maxSum = runTotal؛
}
واپسی زیادہ سے زیادہ رقم
}
دی گئی صف (ویکٹر) کا سائز، N کا تعین کیا جاتا ہے۔ متغیر، maxSum ممکنہ زیادہ سے زیادہ رقموں میں سے ایک ہے۔ ایک صف میں کم از کم ایک زیادہ سے زیادہ رقم ہوتی ہے۔ متغیر، runTotal ہر انڈیکس پر چلنے والے کل کی نمائندگی کرتا ہے۔ وہ دونوں صف کی پہلی قدر کے ساتھ شروع کیے گئے ہیں۔ اس الگورتھم میں، اگر صف میں اگلی ویلیو رننگ ٹوٹل سے زیادہ ہے تو اگلی ویلیو نئی چل رہی ٹوٹل بن جائے گی۔
لوپ کے لیے ایک اہم ہے۔ سکیننگ 1 سے شروع ہوتی ہے نہ کہ صفر کی وجہ سے متغیرات، maxSum اور runTotal سے A[0] جو کہ دی گئی صف کا پہلا عنصر ہے۔
فار لوپ میں، پہلا بیان تمام پچھلی قدروں کی جمع شدہ رقم میں موجودہ قدر کو شامل کر کے عارضی طور پر چلنے والے کل کا تعین کرتا ہے۔
اگلا، ایک if/else تعمیر ہے۔ اگر اکیلے موجودہ قدر اب تک کے چلنے والے کل سے زیادہ ہے، تو وہ واحد قدر چل رہی کل بن جاتی ہے۔ یہ کارآمد ہے خاص طور پر اگر دی گئی صف میں تمام قدریں منفی ہوں۔ اس صورت میں، صرف سب سے زیادہ منفی قدر ہی زیادہ سے زیادہ قدر (جواب) بن جائے گی۔ اگر اکیلے موجودہ قدر اب تک کے عارضی رننگ کل سے زیادہ نہیں ہے، تو رننگ ٹوٹل پچھلی رننگ ٹوٹل اور موجودہ ویلیو بن جاتا ہے، - یہ if/else کنسٹرکٹ کا دوسرا حصہ ہے۔
فار لوپ میں آخری کوڈ سیگمنٹ سابقہ ترتیب (ذیلی صف) کے لیے کسی بھی سابقہ زیادہ سے زیادہ رقم اور موجودہ ترتیب کے لیے کسی بھی موجودہ زیادہ سے زیادہ رقم کے درمیان انتخاب کرتا ہے۔ اس لیے اعلیٰ قدر کا انتخاب کیا جاتا ہے۔ ایک سے زیادہ زیادہ سے زیادہ ذیلی صف کا مجموعہ ہو سکتا ہے۔ نوٹ کریں کہ رننگ ٹوٹل بڑھے گا اور گرے گا، کیونکہ صف کو بائیں سے دائیں اسکین کیا جاتا ہے۔ یہ گرتا ہے کیونکہ یہ منفی اقدار کو پورا کرتا ہے۔
حتمی منتخب کردہ زیادہ سے زیادہ ذیلی صف کی رقم فار لوپ کے بعد واپس کی جاتی ہے۔
Kadane کے الگورتھم فنکشن کے لیے موزوں 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 << نیٹ4 << 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 > F = { - 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
یہاں ہر سطر کا جواب، ترتیب میں دی گئی صف سے مساوی ہے۔
نتیجہ
Kadane کے الگورتھم کے لیے وقت کی پیچیدگی O(n) ہے، جہاں n دی گئی صف میں عناصر کی تعداد ہے۔ زیادہ سے زیادہ ذیلی صف کے مسئلے کے لیے اس بار کی پیچیدگی سب سے تیز ہے۔ دوسرے الگورتھم ہیں جو سست ہیں۔ Kadane کے الگورتھم کا خیال یہ ہے کہ رننگ کل کو انجام دیا جائے، جبکہ زیادہ سے زیادہ رقوم کا آپس میں موازنہ کرتے ہوئے، دی گئی صف میں بائیں سے دائیں حرکت کرتے ہوئے۔ اگر اکیلے موجودہ قدر اب تک کے چلنے والے کل سے زیادہ ہے، تو وہ واحد قدر نئی چل رہی کل بن جاتی ہے۔ بصورت دیگر، نیا رننگ ٹوٹل پچھلی رننگ کل کے علاوہ موجودہ عنصر ہے، جیسا کہ متوقع ہے، جیسا کہ دی گئی صف کو اسکین کیا گیا ہے۔
مختلف ممکنہ ذیلی صفوں کے لیے ایک سے زیادہ زیادہ سے زیادہ رقم ہو سکتی ہے۔ سب سے زیادہ زیادہ سے زیادہ رقم، تمام ممکنہ ذیلی صفوں کے لیے منتخب کی جاتی ہے۔
منتخب کردہ زیادہ سے زیادہ رقم کی حد کے لیے محدود اشاریہ جات کیا ہیں؟ - یہ کسی اور وقت کے لئے بحث ہے!
کریس