Kadane Algorithm से Maximum Subarray
सबसे बड़े sum वाला contiguous भाग खोजें।
Kadane Algorithm से Maximum Subarray क्या है?
समस्या क्या है
किसी stock के लिए दिनों का सबसे अच्छा दौर कौन सा था, points में सबसे लंबी जीत की लकीर, किसी यात्रा का सबसे फ़ायदेमंद हिस्सा? ये सब maximum-subarray सवाल हैं। हर शुरुआत और अंत जाँचना धीमा है; Kadane का एल्गोरिदम इसे एक pass में हल करता है।
ऐसे समझें
Kadane का एल्गोरिदम ऐसा है जैसे किसी रास्ते पर चलते हुए सोना उठाना और toll भरना। आप अपने मौजूदा हिस्से के लिए एक चलता हुआ बटुआ रखते हैं। जब बटुआ negative हो जाए, तो उसे साथ रखना सिर्फ़ नुकसान है, इसलिए आप उसे छोड़कर नए सिरे से शुरू करते हैं। आप यह भी याद रखते हैं कि अब तक का सबसे भरा बटुआ कितना था।
current = max(value, current + value)👛 बटुआ रखिए, या अगर वह बदतर है तो नए सिरे से शुरू कीजिएbest = max(best, current)🏆 अब तक का सबसे भरा बटुआ याद रखिएcurrent = best = values[0]🚩 पहले हिस्से से शुरू कीजिए6💰 सबसे अच्छा हिस्सा: 4, -1, 2, 1Maximum subarray समस्या लिस्ट में लगातार आइटम का सबसे बड़ा जोड़ माँगती है; Kadane का एल्गोरिदम हर position पर ख़त्म होने वाला सबसे अच्छा जोड़ ट्रैक करके इसे O(n) समय में हल करता है।
मुख्य बातें
currentउस दौर का सबसे अच्छा जोड़ है जो मौजूदा वैल्यू पर ख़त्म होता है।current = max(value, current + value)नया दौर शुरू करता है जब पुराना दौर सिर्फ़ जोड़ घटाएगा।best = max(best, current)अब तक कहीं भी देखा गया सबसे अच्छा जोड़ रखता है।- दोनों को
values[0]से शुरू करने पर सिर्फ़ negative संख्याओं वाली लिस्ट भी काम करती है।
इसका उपयोग कब करें?
- Time series में सबसे अच्छा दौर: मुनाफ़ा, scores, तापमान।
- एक pass वाला क्लासिक dynamic programming विचार सीखना।
- Arrays पर इंटरव्यू सवाल।
कब ज़रूरत नहीं
- आपको सबसे अच्छे दौर की शुरुआत और अंत चाहिए: जोड़ के साथ indexes भी ट्रैक कीजिए।
- वैल्यू किसी अर्थपूर्ण क्रम में नहीं हैं: तब लगातार दौरों का कोई मतलब नहीं।
उदाहरण कोड
def maximum_subarray_sum(values):
current = best = values[0]
for value in values[1:]:
current = max(value, current + value)
best = max(best, current)
return best
print(maximum_subarray_sum([-2, 1, -3, 4, -1, 2, 1, -5, 4]))
अपेक्षित आउटपुट
6
यह कैसे काम करता है
एक pass पर्याप्त है: समय O(n) और memory O(1) है।
मान बदलें और Python इंस्टॉल किए बिना CodeUtility ऑनलाइन Python कंपाइलर में प्रोग्राम चलाएँ।
अभ्यास के कार्य
बड़े dataset पर जाने से पहले input बदलें और edge cases की जाँच करें।
- खाली input, एक element और duplicate values जाँचें।
- हर चरण के बाद state दिखाएँ।
- Performance को दूसरे solution से तुलना करें।
आम गलतियाँ
0 से शुरू करना
सारे negative इनपुट पर जवाब गलती से 0 आएगा।
current = best = 0
current = best = values[0]
यह पाठ पूरा कर लिया?
अपनी प्रगति ट्रैक करने के लिए इसे सीखा हुआ मार्क करें।
चैलेंज से अभ्यास करें
इस पाठ में सीखी बात से एक असली समस्या हल करें। हर चैलेंज ब्राउज़र में चलता है, तुरंत टेस्ट और AI रिव्यू के साथ।
- Sliding Window Maximum Report the maximum of every window of k numbers. कठिन
- Largest Adjacent-Digit Product Take every contiguous window of span digits and multiply its digits. मध्यम