Kadane Algorithm से Maximum Subarray
हर position पर तय होता है कि पिछला subarray जारी रखें या नया शुरू करें।
Kadane Algorithm से Maximum Subarray क्या है?
हर position पर तय होता है कि पिछला subarray जारी रखें या नया शुरू करें।
सबसे बड़े sum वाला contiguous भाग खोजें।
इसका उपयोग कब करें?
- Algorithms और data structures की कार्यप्रणाली समझें।
- हर चरण देखें और edge cases जाँचें।
- समय और memory की जटिलता की तुलना करें।
उदाहरण कोड
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]))अपेक्षित आउटपुट
6यह कैसे काम करता है
एक pass पर्याप्त है: समय O(n) और memory O(1) है।
मान बदलें और Python इंस्टॉल किए बिना CodeUtility ऑनलाइन Python कंपाइलर में प्रोग्राम चलाएँ।
अभ्यास के कार्य
बड़े dataset पर जाने से पहले input बदलें और edge cases की जाँच करें।
- खाली input, एक element और duplicate values जाँचें।
- हर चरण के बाद state दिखाएँ।
- Performance को दूसरे solution से तुलना करें।