এই আর্টিকেলে, আমরা একটি দেওয়া ম্যাট্রিক্স বা ২-ডি অ্যারেতে সর্বোচ্চ সম (maximum sum) वाले পেয়ার খুঁজে বের করার কথা আলোচনা করব। উদাহরণস্বরূপ:
Input : matrix[m][n] = { { 3, 5, 2 }, { 2, 6, 47 }, { 1, 64, 66 } } Output : 130 Explanation : সর্বোচ্চ সম 130, উপাদান পেয়ার 64 এবং 66 থেকে। Input : matrix[m][n] = { { 55, 22, 46 }, { 6, 2, 1 }, { 3, 24, 52 } } Output : 107 Explanation : সর্বোচ্চ সম 107, উপাদান পেয়ার 55 এবং 52 থেকে।
সমাধানের পদ্ধতি
দেওয়া সমস্যা সমাধানের জন্য বিভিন্ন প্রক্রিয়া সংক্ষিপ্তে আলোচনা করব।
ব্রুট-ফোর্স পদ্ধতি
একটি ব্রুট-ফোর্স পদ্ধতি প্রয়োগ করা যায়, অর্থাৎ MAX ভেরিয়েবলকে প্রথম দুটি উপাদানের যোগফলে ইনিশিয়ালাইজ করে তারপর অ্যারেটি ট্রাভার্স করে প্রতিটি পেয়ারের যোগফল চেক করুন যদি MAX থেকে বড় হয় তবে MAX কে নতুন যোগফলে আপডেট করুন। কিন্তু এই প্রক্রিয়া বেশি সময় নেবে O((m*n)2) টাইম কমপ্লেক্সিটির সাথে।
দক্ষ পদ্ধতি
একটি দক্ষ পদ্ধতি প্রয়োগ করা যায়, অর্থাৎ দুটি ভেরিয়েবল MAX1 এবং MAX2 কে ০ দিয়ে ইনিশিয়ালাইজ করে ২-ডি অ্যারেটি ট্রাভার্স করুন; চেক করুন বর্তমান উপাদানটি MAX1 চেয়ে বড় কিনা। হ্যাঁ হলে, MAX2 কে MAX1 দিয়ে রিপ্লেস করুন এবং MAX1 কে বর্তমান উপাদান দিয়ে। এইভাবে আমরা দুটি সর্বোচ্চ সংখ্যা খুঁজে পাব, এবং স্বভাবতঃ দুটি সর্বোচ্চ সংখ্যার যোগফলই সর্বোচ্চ হবে।
উদাহরণ
#include <bits/stdc++.h> using namespace std; int main() { int m = 3, n = 3; // ম্যাট্রিক্স মান দিয়ে ইনিশিয়ালাইজ int matrix[m][n] = { { 55, 22, 46 }, { 6, 2, 1 }, { 3, 24, 52 } }; // দুটি সর্বোচ্চ সংখ্যা রাখতে MAX1 এবং MAX2 ইনিশিয়ালাইজ int MAX1 = INT_MIN; int MAX2 = INT_MIN; int result; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { // চেক করুন উপাদানটি MAX1 চেয়ে বড় কিনা। if (matrix[i][j] > MAX1) { MAX2 = MAX1; MAX1 = matrix[i][j]; } // চেক করুন বর্তমান উপাদানটি MAX1 এবং MAX2-এর মাঝপথে আছে কিনা। else if (matrix[i][j] > MAX2 && matrix[i][j] <= MAX1) { MAX2 = matrix[i][j]; } } } // দুটি সর্বোচ্চ সংখ্যা যোগ করে সর্বোচ্চ সম ক্যালকুলেট করুন। result = MAX1 + MAX2; cout << "maximum sum in Matrix : " << result ; return 0; }
আউটপুট
maximum sum in Matrix : 107
উপরোক্ত কোডের ব্যাখ্যা
- ২-ডি অ্যারেতে উপাদান সংরক্ষণ এবং MAX1 ও MAX2 কে INT_MIN দিয়ে ইনিশিয়ালাইজ।
- ম্যাট্রিক্স ট্রাভার্স করুন।
- যদি বর্তমান উপাদান MAX1 চেয়ে বড় হয়, তবে MAX2 কে MAX1 দিয়ে রিপ্লেস করুন এবং MAX1 কে বর্তমান উপাদান দিয়ে।
- যদি বর্তমান উপাদান MAX1 চেয়ে ছোট এবং MAX2 চেয়ে বড় হয়, তবে MAX2 কে বর্তমান উপাদান দিয়ে রিপ্লেস করুন।
- ফলাফল ক্যালকুলেট করুন MAX1 এবং MAX2 যোগ করে এবং প্রিন্ট করুন।
উপসংহার
এই আর্টিকেলে, আমরা একটি দেওয়া ম্যাট্রিক্সে সর্বোচ্চ সম والے পেয়ার খুঁজে বের করার কথা আলোচনা করেছি। আমরা সমাধানের পদ্ধতি আলোচনা করেছি এবং এর জন্য C++ কোডও আলোচনা করেছি। একই কোডটি Java, C, Python ইত্যাদি অন্য ভাষায়ও লিখা যায়। আশা করি আপনি এই আর্টিকেলটিকে উপকারী পাবেন।
