सबसे लंबी बढ़ती हुई उप अनुक्रम 1 (Longest Increasing Subsequence 1)
आपको
n पूर्णांकों का एक array दिया गया है। आपका कार्य है इस array की सबसे लंबी बढ़ती हुई उप अनुक्रम (Longest Increasing Subsequence) खोजना। यदि ऐसी कई उप अनुक्रम मौजूद हों, तो आप किसी भी एक को आउटपुट कर सकते हैं।किसी array की उप अनुक्रम वह क्रम होता है जो array के कुछ (संभवतः शून्य) तत्त्वों को हटाकर प्राप्त किया जाता है, लेकिन शेष तत्त्वों का क्रम वही बना रहता है। उदाहरण के लिए, यदि array है , तो इस array की एक उप अनुक्रम है। लेकिन इसकी उप अनुक्रम नहीं है क्योंकि इसमें तत्त्वों का क्रम बरकरार नहीं रखा गया है।
💡
किसी array की बढ़ती हुई उप अनुक्रम वह उप अनुक्रम होती है जिसमें सभी तत्त्व बढ़ते क्रम में हों। उदाहरण के लिए, यदि array है , तो इस array की एक बढ़ती हुई उप अनुक्रम है। लेकिन बढ़ती हुई उप अनुक्रम नहीं कही जा सकती, क्योंकि उसके तत्त्व बढ़ते क्रम में नहीं हैं।
इनपुट
इनपुट की पहली पंक्ति में एक एकल पूर्णांक
n (1 ≤ n ≤ 1000) होता है, जो array की लंबाई को दर्शाता है।इनपुट की दूसरी पंक्ति में
n स्पेस-उपयोगी पूर्णांक होते हैं (), जो array के तत्त्वों का प्रतिनिधित्व करते हैं।आउटपुट
प्रोग्राम को array की सबसे लंबी बढ़ती हुई उप अनुक्रम की लंबाई प्रिंट करनी चाहिए।
उदाहरण
Input | Output |
8
1 3 2 4 5 2 6 5 | 5 |
6
10 9 2 5 3 7 | 3 |
व्याख्या
- पहले उदाहरण में, array की सबसे लंबी बढ़ती हुई उप अनुक्रम है।
- दूसरे उदाहरण में, array की सबसे लंबी बढ़ती हुई उप अनुक्रम है।
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB