हमें कंटेनर की दीवारों की ऊंचाई की एक सरणी दी गई है। लक्ष्य उस कंटेनर को ढूंढना है जिसमें पानी की अधिकतम मात्रा हो सकती है। चूंकि दीवारों की ऊंचाई एक सरणी के तत्व हैं, उनके बीच की दूरी को दो दीवारों के बीच की चौड़ाई के रूप में माना जाता है। उदाहरण के लिए, Arr[i] और Arr[j] की दीवारों के बीच j-i चौड़ाई है ( 0<=i
तो पानी की ऊंचाई कम ऊंचाई तक होगी, अगर Arr[i]
हमें ऐसे अधिकतम क्षेत्र का पता लगाना है।
इनपुट
Arr[]= { 5,1,2,3,5 }
आउटपुट
Maximum water area : 20
स्पष्टीकरण
जैसा कि चित्र में दिखाया गया है, दीवार की ऊंचाई के लिए 5,1,2,3 और दीवारों के बीच अधिकतम चौड़ाई है
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
अधिकतम क्षेत्र कंटेनर में अधिकतम पानी होगा, क्षेत्रफल =20, दीवारें Arr[0] और Arr[4]
इनपुट
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
अधिकतम क्षेत्र कंटेनर में अधिकतम पानी होगा, क्षेत्रफल =16, दीवारें Arr[0] और Arr[4]
नीचे दिए गए प्रोग्राम में इस्तेमाल किया गया तरीका इस प्रकार है
-
पूर्णांक सरणी दीवारों [] में दीवारों की ऊंचाई होती है।
-
फंक्शन मोस्टवाटर (इंट ए [], इंट लेन) ऊंचाई की सरणी लेता है और नहीं। इसमें मौजूद तत्वों की संख्या और अधिकतम पानी के साथ कंटेनर का क्षेत्र लौटाता है क्योंकि केवल ऊंचाई और चौड़ाई उपलब्ध है।
-
सरणी को दोनों सिरों से पार करना शुरू करने के लिए हम दो अनुक्रमणिका r=len-1 और l=0 लेते हैं।
-
पूर्णांक क्षेत्र और मैक्सारिया का उपयोग वर्तमान कंटेनर के क्षेत्र और अब तक पाए गए अधिकतम कंटेनर क्षेत्र को संग्रहीत करने के लिए किया जाता है। प्रारंभ में 0
-
int minwall,lwall,rwall बाईं दीवार की ऊंचाई (A[l] ), दाहिनी दीवार (A[r] ), और lwall और rwall की न्यूनतम ऊंचाई को संग्रहीत करता है;
-
जबकि (l
-
दो दीवारों के बीच की चौड़ाई इंडेक्स का अंतर है ( r-l )
-
पानी/कंटेनर के क्षेत्रफल को मिनवॉल* (आर-एल) और अद्यतन क्षेत्र के रूप में परिकलित करें।
-
यह सभी दीवारों के लिए करें, यदि वर्तमान क्षेत्र अब तक अधिकतम है तो अधिकतम क्षेत्र अपडेट करें।
-
अंत में मैक्सारिया में अधिकांश पानी के साथ कंटेनर का वांछित क्षेत्र होगा।
- परिणामस्वरूप मैक्सरिया लौटाएं।
उदाहरण
#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