अधिकतम योग सबएरे
आपको
n पूर्णांकों वाले एक array (ऐरे) में उस लगातार (contiguous) subarray (सबएरे) को खोजना है, जिसका मूल्यों का योग अधिकतम हो।इनपुट
इनपुट की पहली पंक्ति में एक पूर्णांक
n दिया गया है – यह array में मौजूद तत्वों की कुल संख्या दर्शाता है (1 ≤ n ≤ )।अगली पंक्ति में
n पूर्णांक स्पेस के साथ दिए जाते हैं, जो array के तत्वों का प्रतिनिधित्व करते हैं ()।आउटपुट
कार्यक्रम को केवल एक पूर्णांक प्रिंट करना चाहिए, जो दिए गए array में उपलब्ध किसी भी subarray का अधिकतम संभव योग हो।
उदाहरण
इनपुट | आउटपुट |
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 → हाइलाइट किए गए subarray का योग (4 - 1 + 3 + 1) = 7
- 1 -2
3 4 -3 1 7-10 -20 4 → 3 + 4 -3 + 1 + 7 = 12
क्या आप इसे और बेहतर बना सकते हैं 😎?
इस समस्या को बिना किसी अतिरिक्त array का उपयोग किए भी हल किया जा सकता है। क्या आप ऐसा कर पाएंगे?
Constraints
Time limit: 6 seconds
Memory limit: 512 MB
Output limit: 1 MB