डिवाइड एंड कॉन्कर एल्गोरिथ्म के साथ अधिकतम योग उप-सरणी
एक ऐसे ऐरे में, जिसमें
n पूर्णांक हैं, डिवाइड एंड कॉन्कर (divide & conquer) तकनीक का उपयोग करके उस सन्निहित (contiguous) उप-सरणी को खोजें, जिसका समग्र मानों का योग अधिकतम हो।इनपुट
इनपुट की पहली पंक्ति में एक पूर्णांक
n होता है, जो ऐरे में मौजूद तत्त्वों की संख्या को दर्शाता है (1 ≤ n ≤ )।अगली पंक्ति में स्पेस से अलग किए गए
n पूर्णांक हैं, जो ऐरे के तत्त्वों का प्रतिनिधित्व करते हैं ।आउटपुट
कार्यक्रम को एक ही पूर्णांक प्रिंट करना चाहिए, जो दी गई ऐरे में किसी भी उप-सरणी का सर्वाधिक सम्भव योग हो।
उदाहरण
इनपुट | आउटपुट |
9
-2 1 -3 4 -1 3 1 -4 -2 | 7 |
10
1 -2 3 4 -3 1 7 -10 -20 4 | 12 |
व्याख्या
- -2 1 -3
4 -1 3 1-4 -2 → चिह्नित उप-सरणी का योग (4 - 1 + 3 + 1) = 7
- 1 -2
3 4 -3 1 7-10 -20 4 → 3 + 4 -3 + 1 + 7 = 12
Constraints
Time limit: 5 seconds
Memory limit: 512 MB
Output limit: 1 MB