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