हिस्टोग्राम में सबसे बड़ा आयताकार क्षेत्रफल
आपको एक हिस्टोग्राम में बारों की ऊँचाइयों का प्रतिनिधित्व करने वाले
n संख्याएँ दी गई हैं। आपका कार्य हिस्टोग्राम में, इन बारों की सीमाओं के अंदर रहते हुए, प्राप्त होने वाले अधिकतम क्षेत्रफल की गणना करना है।इस हिस्टोग्राम में प्रत्येक बार की चौड़ाई 1 होती है, जबकि ऊँचाइयाँ किसी भी गैर-ऋणात्मक पूर्णांक हो सकती हैं।
इनपुट
इनपुट की पहली पंक्ति में एकमात्र पूर्णांक
n (1 ≤ n ≤ ) दिया जाता है।अगली पंक्ति में स्पेस द्वारा अलग किए गए
n पूर्णांक होते हैं: , जिनके मान (0 ≤ ≤ ) हो सकते हैं।आउटपुट
कार्यक्रम को हिस्टोग्राम की इन बारों से प्राप्त होने वाले अधिकतम संभव क्षेत्रफल को प्रिंट करना चाहिए।
उदाहरण
इनपुट | आउटपुट |
8
6 2 5 4 5 1 6 1 | 12 |
संकेत
हिस्टोग्राम के प्रत्येक तत्व के लिए, आप दो संख्याओं की पहचान कर सकते हैं—बाएँ ओर और दाएँ ओर का वह सबसे निकटवर्ती छोटा तत्व, जो वर्तमान तत्व से कम ऊँचाई रखता हो। यह जानकारी पर्याप्त होती है उस आयत के क्षेत्रफल की गणना करने के लिए, जिसकी ऊँचाई वर्तमान बार के बराबर है।
Constraints
Time limit: 4 seconds
Memory limit: 512 MB
Output limit: 1 MB