अधिकतम उपऐरे और अधिकतम गुणनफल उपऐरे
maximum-sum-subarray पर Kadane का एल्गोरिदम लागू कीजिए और गुणनफल वाले रूप के लिए अधिकतम तथा न्यूनतम दोनों मानों का रिकॉर्ड रखकर इसे बढ़ाइए।
अधिकतम उपऐरे और अधिकतम गुणनफल उपऐरे, CoddyKit पर DSA Interview Prep का एक निःशुल्क पाठ है। यह 4 में से 2वाँ पाठ है। इस अध्ययन पथ के 3 तक कोई भी पाठ पूरा पढ़ना निःशुल्क है — इसके बाद CoddyKit PRO हर पाठ अनलॉक करता है, साथ ही अंतर्निर्मित कोड संपादक और चौबीसों घंटे एआई शिक्षक के साथ व्यावहारिक अभ्यास भी उपलब्ध कराता है। यह DSA Interview Prep सीखने के मार्ग का हिस्सा है और आपकी प्रगति वेब तथा CoddyKit ऐप पर सिंक होती रहती है। DSA Interview Prep पाठ्यक्रम में कुल 4 पाठ शामिल हैं।
अधिकतम योग उप-सरणी की समस्या
अधिकतम उप-सरणी समस्या में आपको संख्याओं की एक-आयामी सरणी के भीतर ऐसी सन्निहित उप-सरणी ढूँढ़नी होती है जिसका योग सबसे बड़ा हो। उदाहरण के लिए, [-2, 1, -3, 4, -1, 2, 1, -5, 4] में [4, -1, 2, 1] उप-सरणी का योग 6 है, जो अधिकतम है। पूर्ण-खोज वाली O(n²) विधि सभी उप-सरणियों की जाँच करती है, लेकिन कडेन का एल्गोरिदम इसे O(n) में हल करता है।
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
# Brute force: O(n^2)
max_sum = float('-inf')
for i in range(len(nums)):
curr = 0
for j in range(i, len(nums)):
curr += nums[j]
max_sum = max(max_sum, curr)
print(max_sum) # 6कडेन के एल्गोरिदम की समझ
कडेन का एल्गोरिदम सरणी में केवल एक बार आगे बढ़ता है और एक संचयी current_sum बनाए रखता है। प्रत्येक तत्व पर आपको तय करना होता है: क्या मौजूदा उप-सरणी को बढ़ाना बेहतर है, या इस तत्व से नई शुरुआत करना? यदि current_sum ऋणात्मक हो जाता है, तो वह भविष्य की किसी भी उप-सरणी को केवल नुकसान पहुँचाएगा, इसलिए नई शुरुआत कीजिए। पुनरावृत्ति current_sum = max(num, current_sum + num) है।
def max_subarray(nums):
max_sum = current_sum = nums[0]
for num in nums[1:]:
# Extend or start fresh?
current_sum = max(num, current_sum + num)
max_sum = max(max_sum, current_sum)
return max_sum
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(max_subarray(nums)) # 6कडेन के एल्गोरिदम का अनुरेखण
आइए [-2, 1, -3, 4, -1, 2, 1, -5, 4] पर कडेन के एल्गोरिदम का अनुरेखण करें: शुरुआत में वर्तमान=-2, अधिकतम=-2। 1 पर: वर्तमान=अधिकतम(1,-2+1)=1, अधिकतम=1। -3 पर: वर्तमान=अधिकतम(-3,1-3)=-2, अधिकतम=1। 4 पर: वर्तमान=अधिकतम(4,-2+4)=4, अधिकतम=4। -1 पर: वर्तमान=3, अधिकतम=4। 2 पर: वर्तमान=5, अधिकतम=5। 1 पर: वर्तमान=6, अधिकतम=6। -5 पर: वर्तमान=1। 4 पर: वर्तमान=5, अधिकतम=6। एल्गोरिदम सही रूप से सूचकांक 6 पर समाप्त होने वाली उप-सरणी को सर्वोत्तम पहचानता है।
def max_subarray_trace(nums):
curr = max_sum = nums[0]
for i, num in enumerate(nums[1:], 1):
new_curr = max(num, curr + num)
max_sum = max(max_sum, new_curr)
print(f'i={i}, num={num}, curr: {curr}->{new_curr}, max={max_sum}')
curr = new_curr
return max_sum
max_subarray_trace([-2, 1, -3, 4, -1, 2, 1, -5, 4])वास्तविक उप-सरणी लौटाना
यदि साक्षात्कारकर्ता आपसे उप-सरणी को स्वयं लौटाने के लिए कहता है, केवल योग को नहीं, तो आपको आरंभ और अंत के सूचकांकों का लेखा रखना होगा। जब आप नई शुरुआत करें (क्योंकि num > current_sum + num), तो temp_start को अद्यतन कीजिए। जब आप max_sum को अद्यतन करें, तो temp_start को start के रूप में और वर्तमान सूचकांक को end के रूप में सहेजिए। इससे उसी O(n) एल्गोरिदम में केवल O(1) अतिरिक्त लागत जुड़ती है।
def max_subarray_indices(nums):
max_sum = curr = nums[0]
start = end = temp_start = 0
for i in range(1, len(nums)):
if nums[i] > curr + nums[i]:
curr = nums[i]
temp_start = i
else:
curr += nums[i]
if curr > max_sum:
max_sum = curr
start, end = temp_start, i
return max_sum, nums[start:end+1]
print(max_subarray_indices([-2, 1, -3, 4, -1, 2, 1, -5, 4]))
# (6, [4, -1, 2, 1])अधिकतम गुणनफल उप-सरणी की समस्या
अधिकतम गुणनफल उप-सरणी समस्या योग वाले रूप से अधिक कठिन है, क्योंकि इसमें ऋणात्मक संख्याएँ होती हैं। दो ऋणात्मक संख्याओं का गुणनफल धनात्मक होता है, इसलिए किसी बहुत ऋणात्मक गुणनफल को दूसरी ऋणात्मक संख्या से गुणा करने पर वह अधिकतम बन सकता है। [2, 3, -2, 4] के लिए उत्तर 6 ([2, 3]) है। [-2, 0, -1] के लिए उत्तर 0 है। हमें प्रत्येक चरण पर अधिकतम और न्यूनतम दोनों गुणनफलों का लेखा रखना होगा।
nums = [2, 3, -2, 4]
# [2,3,-2,4]: products [2, 6, -12, -48]
# subarrays: [2]=2, [2,3]=6, [3]=3, etc.
# max is 6 from subarray [2,3]
nums2 = [-2, 3, -4]
# [-2]*3*[-4] = 24
# negative*negative=positive!
print('Expected:', 24)अधिकतम और न्यूनतम दोनों गुणनफलों का लेखा रखना
मुख्य समझ यह है: प्रत्येक स्थान पर वर्तमान अधिकतम गुणनफल num, max_so_far * num या min_so_far * num में से एक होता है। अंतिम विकल्प तब सहायक होता है जब कोई ऋणात्मक संख्या न्यूनतम को अधिकतम में बदल देती है। न्यूनतम के लिए भी यही बात लागू होती है। पिछले मानों का उपयोग करके दोनों cur_max और cur_min को एक साथ अद्यतन कीजिए, ताकि उसी चरण में पहले से अद्यतन मानों का उपयोग न हो।
def max_product(nums):
max_prod = min_prod = result = nums[0]
for num in nums[1:]:
# All three candidates for new max
candidates = (num, max_prod * num, min_prod * num)
max_prod, min_prod = max(candidates), min(candidates)
result = max(result, max_prod)
return result
print(max_product([2, 3, -2, 4])) # 6
print(max_product([-2, 3, -4])) # 24
print(max_product([-2, 0, -1])) # 0
print(max_product([-2])) # -2न्यूनतम गुणनफल का महत्व
[-3, -10, 5] पर विचार कीजिए। -3 को संसाधित करने के बाद: अधिकतम=-3, न्यूनतम=-3। -10 के बाद: संभावित मान हैं (-10, 30, 30) → अधिकतम=30, न्यूनतम=-10। 5 के बाद: संभावित मान हैं (5, 150, -50) → अधिकतम=150। min_prod का लेखा रखे बिना आप उस परिवर्तन को खो देंगे जो तब होता है जब बहुत ऋणात्मक न्यूनतम को दूसरी ऋणात्मक संख्या से गुणा किया जाता है। पुराने मानों को पढ़ने से जुड़ी त्रुटि से बचने के लिए हमेशा एक ही पिछले मानों से max और min दोनों की गणना कीजिए।
def max_product_traced(nums):
max_p = min_p = result = nums[0]
for num in nums[1:]:
prev_max, prev_min = max_p, min_p
max_p = max(num, prev_max * num, prev_min * num)
min_p = min(num, prev_max * num, prev_min * num)
result = max(result, max_p)
print(f'num={num}: max_p={max_p}, min_p={min_p}')
return result
max_product_traced([-3, -10, 5])
# max_p after -10: 30 (flip!)
# max_p after 5: 150शून्य गुणनफल को फिर से शुरू करता है
सरणी में मौजूद शून्य दोनों संचयी गुणनफलों को शून्य पर लौटा देता है और प्रभावी रूप से सरणी को स्वतंत्र उप-सरणियों में बाँट देता है। जब num = 0 हो, तो max_prod * 0 = 0 और min_prod * 0 = 0 दोनों होते हैं, इसलिए तीनों संभावित मान 0 बन जाते हैं और पिछले परिणाम का अधिकतम सुरक्षित रहता है। किसी विशेष परिस्थिति के लिए अलग कोड की आवश्यकता नहीं है — सामान्य सूत्र शून्य को स्वाभाविक रूप से संभालता है।
def max_product(nums):
max_p = min_p = result = nums[0]
for num in nums[1:]:
cands = (num, max_p * num, min_p * num)
max_p, min_p = max(cands), min(cands)
result = max(result, max_p)
return result
# Zero splits array into independent subarrays
print(max_product([3, -1, 4, 0, 2, 5, -1])) # 10 (2*5)
print(max_product([0, 2])) # 2
print(max_product([-1, 0, -2])) # 0वैकल्पिक विधि: बाएँ-दाएँ गुणनफल का क्रमिक परीक्षण
एक वैकल्पिक विधि बाएँ से दाएँ और दाएँ से बाएँ क्रमिक रूप से चलती है तथा शून्य मिलने पर संचयी गुणनफल को 1 पर लौटा देती है। अधिकतम गुणनफल वाली उप-सरणी कभी भी शून्य को पार नहीं करती, इसलिए यदि किसी दिशा में ऋणात्मक संख्या परिणाम को खराब कर देती है, तो उलटी दिशा में किया गया परीक्षण उस बदलाव को पकड़ लेगा। यह विधि सुंदर है, लेकिन साक्षात्कारों में न्यूनतम/अधिकतम का लेखा रखने वाली विधि की अपेक्षा अधिक सामान्य है।
def max_product_sweep(nums):
result = max(nums)
left = right = 1
n = len(nums)
for i in range(n):
left *= nums[i]
right *= nums[n - 1 - i]
result = max(result, left, right)
if left == 0: left = 1
if right == 0: right = 1
return result
print(max_product_sweep([2, 3, -2, 4])) # 6
print(max_product_sweep([-2, 3, -4])) # 24
print(max_product_sweep([-2, 0, -1])) # 0कडेन एल्गोरिदम बनाम गुणनफल: मुख्य अंतर
योग और गुणनफल वाली उप-सरणियाँ महत्वपूर्ण तरीकों से अलग होती हैं। योग के लिए: ऋणात्मक संख्याएँ हमेशा हानिकारक होती हैं, इसलिए लालच-आधारित तरीके से नई शुरुआत कीजिए। गुणनफल के लिए: दो ऋणात्मक संख्याएँ लाभदायक हो सकती हैं, इसलिए आपको दोनों चरम मानों का लेखा रखना होगा। इसके अतिरिक्त, शून्य गुणनफलों के लिए निर्णायक होते हैं, जबकि योग के लिए केवल कुछ हद तक हानिकारक होते हैं। साक्षात्कार में इन अंतरों को स्पष्ट रूप से स्वीकार कीजिए और कोई भी कोड लिखने से पहले समझाइए कि न्यूनतम मान का लेखा रखना क्यों आवश्यक है।
# Max Sum Subarray: O(n) time, O(1) space
def max_sum(nums):
curr = result = nums[0]
for n in nums[1:]:
curr = max(n, curr + n) # restart or extend
result = max(result, curr)
return result
# Max Product Subarray: O(n) time, O(1) space
def max_prod(nums):
lo = hi = result = nums[0]
for n in nums[1:]:
lo, hi = min(n, lo*n, hi*n), max(n, lo*n, hi*n)
result = max(result, hi)
return result
print(max_sum([-2, 1, -3, 4, -1, 2, 1])) # 6
print(max_prod([-2, 3, -4])) # 24जटिलता और साक्षात्कार संबंधी सुझाव
कडेन का एल्गोरिदम (अधिकतम योग) और न्यूनतम/अधिकतम का लेखा रखने वाली विधि (अधिकतम गुणनफल) दोनों O(n) समय और O(1) स्थान में चलते हैं। साक्षात्कार के मुख्य सुझाव: (1) अधिकतम योग के लिए, अपनी जानकारी की व्यापकता दिखाने हेतु विभाजित करो और विजय पाओ वाली O(n log n) वैकल्पिक विधि का उल्लेख कीजिए। (2) अधिकतम गुणनफल के लिए, इस बात पर ज़ोर दीजिए कि पुराने मानों से min_prod और max_prod को एक साथ अद्यतन किया जाता है, ताकि पुराने डेटा का उपयोग न हो। (3) हमेशा स्पष्ट कीजिए: क्या सरणी रिक्त हो सकती है? क्या उप-सरणी का रिक्त न होना आवश्यक है? (हाँ, परंपरा के अनुसार इसका रिक्त न होना आवश्यक है।)
# Both run O(n) time, O(1) space
# Kadane handles: all negative (returns least negative)
# Product handles: zeros (resets naturally), negatives (tracks both extremes)
nums_all_neg = [-5, -2, -8]
print('Max sum (all neg):', max(max(nums_all_neg[0:1]),
max(x for x in nums_all_neg))) # -2
# Correct: return the maximum element when all are negativeत्वरित जाँच
इस पाठ में पढ़ी गई डेटा संरचनाओं और एल्गोरिदम — कोडिंग साक्षात्कार की तैयारी से जुड़ी अवधारणाओं की अपनी समझ जाँचिए।
पाठ का पुनरावलोकन
इस पाठ में आपने सीखा: कडेन का एल्गोरिदम प्रत्येक तत्व पर उप-सरणी को बढ़ाने या नई शुरुआत करने का विकल्प चुनकर O(n) में अधिकतम योग वाली उप-सरणी हल करता है, ऋणात्मक संख्याओं के चिह्न बदलने के कारण अधिकतम गुणनफल वाली उप-सरणी के लिए न्यूनतम और अधिकतम दोनों संचयी गुणनफलों का लेखा रखना आवश्यक है, और शून्य किसी विशेष परिस्थिति वाले कोड के बिना संचयी गुणनफल को स्वाभाविक रूप से फिर से शुरू कर देते हैं। इसके बाद हम एक-आयामी DP तालिका का उपयोग करके वर्ड ब्रेक समस्या का अध्ययन करेंगे।
एआई शिक्षक के साथ Python सीखें — निःशुल्क
अपने ब्राउज़र में वास्तविक कोड लिखें और चलाएँ, चौबीसों घंटे एआई शिक्षक से तुरंत सहायता पाएँ, और वेब या ऐप पर वहीं से शुरू करें जहाँ आपने छोड़ा था।
- पाठ्यक्रम
- 30
- पाठ
- 120
अक्सर पूछे जाने वाले प्रश्न
क्या “अधिकतम उपऐरे और अधिकतम गुणनफल उपऐरे” पाठ निःशुल्क है?
हाँ — DSA Interview Prep अध्ययन पथ के 3 तक कोई भी पाठ, जिसमें “अधिकतम उपऐरे और अधिकतम गुणनफल उपऐरे” भी शामिल है, यहाँ वेब पर पूरा पढ़ना निःशुल्क है। इसके बाद CoddyKit PRO हर पाठ अनलॉक करता है, साथ ही अंतर्निर्मित कोड संपादक और चौबीसों घंटे एआई शिक्षक के साथ इंटरैक्टिव अभ्यास भी उपलब्ध कराता है। DSA Interview Prep पाठ्यक्रम में कुल 4 पाठ शामिल हैं।
“अधिकतम उपऐरे और अधिकतम गुणनफल उपऐरे” में मैं क्या सीखूँगा?
maximum-sum-subarray पर Kadane का एल्गोरिदम लागू कीजिए और गुणनफल वाले रूप के लिए अधिकतम तथा न्यूनतम दोनों मानों का रिकॉर्ड रखकर इसे बढ़ाइए। आप ब्राउज़र में सीधे चलाए जाने वाले व्यावहारिक कोड के साथ DSA Interview Prep का अभ्यास करते हैं, और पाठ पूरा करते समय 24/7 एआई ट्यूटर आपके प्रश्नों के उत्तर देता है।
क्या DSA Interview Prep शुरू करने के लिए मुझे किसी अनुभव की आवश्यकता है?
पहले के अनुभव की आवश्यकता नहीं है। CoddyKit पर DSA Interview Prep शुरुआती से लेकर उन्नत शिक्षार्थियों तक सभी के लिए व्यवस्थित किया गया है, इसलिए आप यहीं से या शुरुआत से सीखना शुरू कर सकते हैं और अपनी गति से आगे बढ़ सकते हैं। यह 4 में से 2वाँ पाठ है।
“अधिकतम उपऐरे और अधिकतम गुणनफल उपऐरे” पाठ पूरा करने में कितना समय लगता है?
CoddyKit का अधिकांश पाठ लगभग 5–10 मिनट में पूरा हो जाता है। हर पाठ छोटा और संवादात्मक है, इसलिए आप लगातार प्रगति करते हैं और वेब या ऐप पर वहीं से सीखना जारी रख सकते हैं जहाँ आपने छोड़ा था।
क्या मैं इस DSA Interview Prep पाठ में कोड लिख और चला सकता हूँ?
हाँ। हर DSA Interview Prep पाठ में एक अंतर्निर्मित कोड संपादक शामिल है, जिससे आप सीधे अपने ब्राउज़र में वास्तविक कोड लिख और चला सकते हैं और तुरंत एआई प्रतिक्रिया पा सकते हैं—स्थानीय सेटअप की आवश्यकता नहीं है।
इस पाठ्यक्रम के सभी पाठ
- House Robber: लेना या छोड़ना पुनरावृत्ति
- अधिकतम उपऐरे और अधिकतम गुणनफल उपऐरे
- Word Break और स्ट्रिंग विभाजन
- Decode Ways और पथों की गिनती