আমাদের পাত্রের দেয়ালের উচ্চতার একটি অ্যারে দেওয়া হয়। লক্ষ্য হল জলের সর্বোচ্চ পরিমাণ ধারণ করতে পারে এমন পাত্র খুঁজে বের করা। যেহেতু দেয়ালের উচ্চতা একটি অ্যারের উপাদান, তাদের মধ্যে দূরত্ব দুটি দেয়ালের মধ্যে প্রস্থ হিসাবে বিবেচিত হয়। উদাহরণস্বরূপ Arr[i] এবং Arr[j] উচ্চতার দেয়ালগুলির মধ্যে j-i প্রস্থ রয়েছে ( 0<=i
সুতরাং পানির উচ্চতা কম উচ্চতা পর্যন্ত হবে, যদি Arr[i]
আমাদের এই ধরনের সর্বাধিক এলাকা খুঁজে বের করতে হবে।
চিত্রে দেখানো হয়েছে, দেয়ালের উচ্চতা 5,1,2,3 এবং দেয়ালের মধ্যে সর্বাধিক প্রস্থ হল
সর্বাধিক এলাকার পাত্রে সর্বাধিক জল থাকবে, এলাকা=20, দেয়াল Arr[0] এবং Arr[4]
সর্বাধিক এলাকার পাত্রে সর্বাধিক জল থাকবে, এলাকা=16, দেয়াল Arr[0] এবং Arr[4]
পূর্ণসংখ্যা অ্যারে দেয়াল [] দেয়ালের উচ্চতা ধারণ করে।
ফাংশন mostwater(int A[], int len) উচ্চতা এবং সংখ্যার অ্যারে নেয়। এটিতে উপাদানগুলির সংখ্যা এবং শুধুমাত্র উচ্চতা এবং প্রস্থ উপলব্ধ থাকায় বেশিরভাগ জল সহ পাত্রের ক্ষেত্রফল প্রদান করে৷
উভয় প্রান্ত থেকে অ্যারে অতিক্রম করা শুরু করতে আমরা r=len-1 এবং l=0 দুটি সূচক নিই।
পূর্ণসংখ্যা এলাকা এবং maxarea বর্তমান কন্টেইনার এলাকা এবং সর্বাধিক কন্টেইনার এলাকা সংরক্ষণ করতে ব্যবহৃত হয় যথাক্রমে। প্রাথমিকভাবে 0
int minwall,lwall,rwall বাম দেয়ালের উচ্চতা ( A[l]), ডান দেয়াল ( A[r]), এবং lwall এবং rwall-এর ন্যূনতম উচ্চতা সংরক্ষণ করে;
যখন ( l
দুই দেয়ালের মধ্যে প্রস্থ হল সূচকের পার্থক্য ( r-l )
মিনওয়াল* ( r-l ) এবং আপডেট এলাকা হিসাবে জল/পাত্রের এলাকা গণনা করুন।
সমস্ত দেয়ালের জন্য এটি করুন, যদি বর্তমান ক্ষেত্রটি সর্বাধিক হয় এখন পর্যন্ত সর্বাধিক আপডেট করুন।
শেষ পর্যন্ত maxarea-এর কাঙ্খিত এলাকা থাকবে বেশির ভাগ জল সহ পাত্রের।ইনপুট
Arr[]= { 5,1,2,3,5 }
আউটপুট
Maximum water area : 20
ব্যাখ্যা
Arr[0] and Arr[4] width=4, area = Arr[0]<=Arr[4] → 5*4=20
Arr[1] and Arr[4] width=3, area = Arr[1]<=Arr[4] → 1*4=4
Arr[2] and Arr[0] or Arr[4] width=4, area = Arr[0]<=Arr[0] → 2*2=4
Arr3] and Arr[0] width=3, area = Arr[0]<=Arr[0] → 3*3=9
Arr[4] and Arr[0] width=4, area = Arr[0]<=Arr[4] → 5*4=20
ইনপুট
Arr[]= { 1, 5, 4, 3, 2, 4 }
আউটপুট
Maximum water area : 16
ব্যাখ্যা
Arr[0] and Arr[5] width=5, area = Arr[0]<=Arr[5] → 1*5= 5
Arr[1] and Arr[5] width=4, area = Arr[1]<=Arr[5] → 4*4=16
Arr[2] and Arr[5] width=3, area = Arr[2]<=Arr[5] → 3*4=12
Arr[3] and Arr[1] width=2, area = Arr[3]<=Arr[1] → 3*2=6
Arr[4] and Arr[1] width=3, area = Arr[1]<=Arr[4] → 2*3=6
Arr[5] and Arr[1] width=4, area = Arr[1]<=Arr[4] → 4*4=16
নিম্নলিখিত প্রোগ্রামে ব্যবহৃত পদ্ধতি
উদাহরণ
#include<iostream>
using namespace std;
int mostwater(int A[], int len){
int r=len-1; //index of right wall of container
int l=0; //index of left wall of container
int area=0,maxarea=0;
int minwall,lwall,rwall;
// int area = 0;
while (l < r){
// Calculating the max area
lwall = A[l]; //height of left wall of container
rwall =A[r]; //height of right wall of container
minwall=lwall<=rwall?lwall:rwall; //min. of two walls is height of water
area=minwall*(r-l); // area is min wall* widht(r-l)
maxarea=area>=maxarea?area:maxarea;
if (l < r)
l += 1;
else
r -= 1;
}
return maxarea;
}
int main(){
int walls[] = {1, 5, 4, 3, 2, 4};
int num = sizeof(walls) / sizeof(walls[0]);
cout << endl <<"Container with Most water has area:"<< mostwater(walls,num);
}
আউটপুট
Container with Most water has area:16