Python एल्गोरिदम

Kadane Algorithm से Maximum Subarray

सबसे बड़े sum वाला contiguous भाग खोजें।

  • मध्यम
  • 2 मिनट में पढ़ें
  • 1 चलाने योग्य उदाहरण

Kadane Algorithm से Maximum Subarray क्या है?

समस्या क्या है

किसी stock के लिए दिनों का सबसे अच्छा दौर कौन सा था, points में सबसे लंबी जीत की लकीर, किसी यात्रा का सबसे फ़ायदेमंद हिस्सा? ये सब maximum-subarray सवाल हैं। हर शुरुआत और अंत जाँचना धीमा है; Kadane का एल्गोरिदम इसे एक pass में हल करता है।

ऐसे समझें

Kadane का एल्गोरिदम ऐसा है जैसे किसी रास्ते पर चलते हुए सोना उठाना और toll भरना। आप अपने मौजूदा हिस्से के लिए एक चलता हुआ बटुआ रखते हैं। जब बटुआ negative हो जाए, तो उसे साथ रखना सिर्फ़ नुकसान है, इसलिए आप उसे छोड़कर नए सिरे से शुरू करते हैं। आप यह भी याद रखते हैं कि अब तक का सबसे भरा बटुआ कितना था।

Toll वाली सड़क से कोड तक
current = max(value, current + value)👛 बटुआ रखिए, या अगर वह बदतर है तो नए सिरे से शुरू कीजिए
best = max(best, current)🏆 अब तक का सबसे भरा बटुआ याद रखिए
current = best = values[0]🚩 पहले हिस्से से शुरू कीजिए
6💰 सबसे अच्छा हिस्सा: 4, -1, 2, 1
जब तक फ़ायदा हो, दौर बढ़ाइए; जब न हो, फिर से शुरू कीजिए।
एक वाक्य में

Maximum subarray समस्या लिस्ट में लगातार आइटम का सबसे बड़ा जोड़ माँगती है; Kadane का एल्गोरिदम हर position पर ख़त्म होने वाला सबसे अच्छा जोड़ ट्रैक करके इसे O(n) समय में हल करता है।

मुख्य बातें

  1. current उस दौर का सबसे अच्छा जोड़ है जो मौजूदा वैल्यू पर ख़त्म होता है।
  2. current = max(value, current + value) नया दौर शुरू करता है जब पुराना दौर सिर्फ़ जोड़ घटाएगा।
  3. best = max(best, current) अब तक कहीं भी देखा गया सबसे अच्छा जोड़ रखता है।
  4. दोनों को values[0] से शुरू करने पर सिर्फ़ negative संख्याओं वाली लिस्ट भी काम करती है।

इसका उपयोग कब करें?

  • Time series में सबसे अच्छा दौर: मुनाफ़ा, scores, तापमान।
  • एक pass वाला क्लासिक dynamic programming विचार सीखना।
  • Arrays पर इंटरव्यू सवाल।

कब ज़रूरत नहीं

  • आपको सबसे अच्छे दौर की शुरुआत और अंत चाहिए: जोड़ के साथ indexes भी ट्रैक कीजिए।
  • वैल्यू किसी अर्थपूर्ण क्रम में नहीं हैं: तब लगातार दौरों का कोई मतलब नहीं।

उदाहरण कोड

कोड चलाएँ →
main.py
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]))
इस उदाहरण के लिए Run बटन बनाएँ

अपेक्षित आउटपुट

6

यह कैसे काम करता है

एक pass पर्याप्त है: समय O(n) और memory O(1) है।

मान बदलें और Python इंस्टॉल किए बिना CodeUtility ऑनलाइन Python कंपाइलर में प्रोग्राम चलाएँ।

अभ्यास के कार्य

बड़े dataset पर जाने से पहले input बदलें और edge cases की जाँच करें।

  1. खाली input, एक element और duplicate values जाँचें।
  2. हर चरण के बाद state दिखाएँ।
  3. Performance को दूसरे solution से तुलना करें।
Python IDE में चलाएँ →

आम गलतियाँ

0 से शुरू करना

सारे negative इनपुट पर जवाब गलती से 0 आएगा।

समस्या
current = best = 0
सुधार
current = best = values[0]

यह पाठ पूरा कर लिया?

अपनी प्रगति ट्रैक करने के लिए इसे सीखा हुआ मार्क करें।

चैलेंज से अभ्यास करें

इस पाठ में सीखी बात से एक असली समस्या हल करें। हर चैलेंज ब्राउज़र में चलता है, तुरंत टेस्ट और AI रिव्यू के साथ।

सभी चैलेंज