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