এটি একটি সি++ প্রোগ্রাম যা হিস্টোগ্রামে (Histogram) সর্বোচ্চ আয়তাকার এরিয়া (Largest Rectangular Area) বের করে।
getArea() ফাংশনের অ্যালগরিদম:
শুরু একটি খালি স্ট্যাক তৈরি করুন। সর্বোচ্চ এরিয়া (largest_area) ইনিশিয়ালাইজ করুন। প্রথম বার থেকে শুরু করে প্রতিটি বার hist[i]-এর জন্য একটি হাইল লুপ করুন, যেখানে i = 0 থেকে n-১: যদি স্ট্যাক খালি থাকে বা hist[i] স্ট্যাকের টপের বার থেকে বেশি হয়, তবে 'i' কে স্ট্যাকে পুশ করুন। অন্যথায় এই বার স্ট্যাকের টপ থেকে ছোট, তবে স্ট্যাকের টপটি বেশি থাকার পর্যંત সরিয়ে ফেলুন। ছোট্ট বার দিয়ে আয়তাকারের এরিয়া ক্যালকুলেট করুন। স্ট্যাকের টপের আগের এলিমেন্ট হল লेफ্ট ইনডেক্স এবং i হল টপের রাইট ইনডেক্স। যদি স্ট্যাক খালি না থাকে তবে বাকি বারগুলো পপ করুন এবং প্রতিটি পপ করা বারকে ছোট্ট বার হিসেবে বিবেচনা করে এরিয়া ক্যালকুলেট করুন। শেষ
উদাহরণ কোড
#include<iostream> #include<stack> using namespace std; int getArea(int hist[], int n) { stack<int> st; int largest_area = 0; int top; int toparea; int i = 0; while (i < n) { if (st.empty() || hist[st.top()] <= hist[i]) st.push(i++); else { top = st.top(); st.pop(); toparea = hist[top] * (st.empty() ? i : i - st.top() - 1); if (largest_area < toparea) largest_area = toparea; } } while (st.empty() == false) { top = st.top(); st.pop(); toparea = hist[top] * (st.empty() ? i : i - st.top() - 1); if (largest_area < toparea) largest_area = toparea; } return largest_area; } int main() { int hist[] = {6,7,4,5,3,2}; int n = sizeof(hist)/sizeof(hist[0]); cout << "Largest area is " << getArea(hist, n); return 0; }
আউটপুট
Largest area is 16
