ম্যাক্সিমাম সাম সাবঅ্যারে (ডায়নামিক এপ্রোচ : Kadane’s Algorithm)
অ্যারের সাথে আমরা সবাই কমবেশি পরিচিত। এক কথায় বলতে গেলে অ্যারে হচ্ছে এমন একটি কনটেইনার যা একই রকম ডাটা টাইপের একটি নির্দিষ্ট সংখ্যক ডাটা সংরক্ষণ করে রাখতে পারে। আবার একটি অ্যারেকে যদি আমরা কয়েকটি ব্লকে ভাগ করি তাহলে প্রতিটি ব্লক হবে ওই অ্যারের এক একটি সাবঅ্যারে।
ধরা যাক, একটি অ্যারে X[3] = {1,2,3}। এই অ্যারের সাবঅ্যারে গুলো হল {1}, {2}, {3}, {1,2}, {2,3} এবং {1,2,3}।
ম্যাক্সিমাম সাম সবঅ্যারে প্রবলেম :
ধরা যাক, n সংখ্যক উপাদানের একটি 0 ইন্ডেক্সড ইন্টিজার অ্যারে দেয়া আছে। আমাদের এই অ্যারের সাবঅ্যারে গুলোর সর্বোচ্চ যোগফলটি বের করতে হবে।
উদাহরনস্বরূপ, উপরের অ্যারেটির কথাই চিন্তা করা যাক। এখানে ম্যাক্সিমাম সাম সাবঅ্যারে হল {8,-1,3,2}, যার যোগফল 12।
এখন এই ম্যাক্সিমাম সাম আমরা কিভাবে বের করব?
Brute Force Approach :
Brute Force এপ্লাই করে আমরা সহজেই সমাধানে পৌঁছাতে পারি। আমরা শুরু থেকে প্রত্যেকটি ইনডেক্সের জন্য সম্ভাব্য সকল সাবঅ্যারে এবং তাদের যোগফল বের করে তাদের মধ্যে ম্যাক্সিমাম যোগফলটি কোনো একটি অ্যারেতে সংরক্ষণ করে রাখতে পারি। ধরা যাক, প্রত্যেকটি ইনডেক্সের ম্যাক্সিমাম সাবঅ্যারে সাম গুলো আমরা current_maximum নামে একটি অ্যারে তে সংরক্ষণ করে রাখব।
একই ভাবে সবগুলো ইনডেক্সের current_maximum যদি আমাদের কাছে থাকে তাহলে আমরা খুব সহজেই বলতে পারি, এই অ্যারের মধ্যকার সর্বোচ্চ এলিমেন্টটি ই আমাদের maximum_sum।
এখানে আমরা প্রতিটি ইনডেক্সের জন্য প্রতিবার আলাদাভাবে current_maximum ক্যালকুলেট করছি। তাহলে এই কোডের টাইম কমপ্লেক্সিটি দাড়ায় O(n²)। অর্থাৎ n এর বড় কোনো মানের জন্য এটি তেমন উপযোগী কোনো সলুশন নয়।
এবার আসি টাইম কমপ্লেক্সিটি কিভাবে কমানো যায় সে বিষয়ে।
Dynamic Approach :
ডায়নামিক প্রোগ্রাম ব্যাবহার করে আমরা খুব কম সময়েই ম্যাক্সিমাম সাম সাবঅ্যারে বের করতে পারি, যেটি Kadane’s Algorithm নামে পরিচিত। এজন্য প্রথমেই জানতে হবে ডায়নামিক প্রোগ্রামিং কি? একটি প্রবলেমকে ছোট ছোট কয়েকটি সাবপ্রবলেমে ভাগ করে, সাবপ্রবলেমগুলোর সলুশন কোনো মেমরিতে সংরক্ষণ করে রাখা এবং প্রতিবার ক্যালকুলেট না করে প্রয়োজন অনুযায়ী ওই মেমোরি থেকে নিয়ে ব্যবহার করাই হল ডায়নামিক প্রোগ্রামিং।
এবার উপরের Brute force সলুশনটাকে একটু উলটো ভাবে চিন্তা করি, অর্থাৎ আমরা শেষ ইন্ডেক্স থেকে current_maximum ক্যালকুলেট করব।
এখন ৩য় ও ৪র্থ এবং ৫ম ও ৬ষ্ঠ ইন্ডেক্সের দিকে লক্ষ্য করি,
উপরের চিত্র থেকে একটি বিষয় স্পষ্ট যে, একটি নির্দিষ্ট ইনডেক্সের current_maximum হয় সেই ইন্ডেক্সের ভ্যালু নিজে অথবা আগের ইন্ডেক্সের current_maximum এবং ঐ ইন্ডেক্সের ভ্যালুর যোগফল।
current_maximum[i] = max(a[i] , current_maximum[i-1] + a[i]) ;
অর্থাৎ পূর্ববর্তী ইন্ডেক্স এর current_maximum জানা থাকলে আমরা খুব সহজেই সেই ইন্ডেক্স এর current_maximum বের করে ফেলতে পারি। এক্ষেত্রে current_maximum[0] = a[0]।
এবং maximum_sum এর জন্য শুরুতে একটি ইন্টিজার ভেরিয়েবল নেগেটিভ ইনফিনিটি দিয়ে ইনিশিয়ালাইজ করে রাখব এবং current_maximum এর ভ্যালু যখনই maximum_sum এর চেয়ে বেশি হবে তখনই maximum_sum আপডেট করব।
এভাবে আমরা সম্পূর্ণ অ্যারেটি একবার অ্যাকসেস করেই Maximum Subarray Sum পেয়ে যাচ্ছি। এবং কাজটি O(n) টাইম কমপ্লেক্সিটি তেই হয়ে যাচ্ছে।
Implementation :
উপরের কোডটিতে , Time Complexity : O(n) এবং Space Complexity : O(n)।
আমরা এই কোডটিকে আরও একটু মোডিফাই করতে পারি, এখানে আমাদের current_maximum গুলো অ্যারেতে সংরক্ষণ করে রাখার কোনো প্রয়োজন নেই। অর্থাৎ আমরা অ্যারের পরিবর্তে একটি ইন্টিজার ভেরিয়েবল দিয়েই কাজটি করতে পারি।
এই কোডের, Time Complexity : O(n) এবং Space Complexity : O(1)।
এখন যদি বলা হয় যে সাবঅ্যারেটির সাম ম্যাক্সিমাম সেই সাবঅ্যাারেটি প্রিন্ট করো। তাহলে?
এক্ষেত্রে আমরা দু’টি ভেরিয়েবলে start index এবং end index সেভ করে রাখব এবং সব শেষে start index থেকে end index পর্যন্ত ভ্যালু গুলো প্রিন্ট করে দিলেই পেয়ে যাব ম্যাক্সিমাম সামের সাবঅ্যারেটি।
একই ভাবে আমরা একটি 2D ম্যাট্রিক্স থেকেও ম্যাক্সিমাম সাবম্যাট্রিক্স বের করতে পারি খুব সহজেই।
আজ এ পর্যন্ত ই। যেকোনো মতামতের জন্য কমেন্ট করার অনুরোধ রইল। সবাই ঘরে থাকুন,সুস্থ থাকুন।
হ্যাপি কোডিং। 😊
