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