प्रश्न और संदर्भ
लंबाई n का एक पूर्णांक ऐरे दिया गया है जिसका अंत उसके प्रारंभ से जुड़ा हुआ है, एक निरंतर सबएरे रैप अराउंड (wrap around) हो सकता है लेकिन एक ही स्थिति का दो बार उपयोग नहीं कर सकता है। किसी गैर-रिक्त सबएरे का अधिकतम योग लौटाएं। साक्षात्कारकर्ता अक्सर उम्मीदवारों से Kadane's algorithm से सर्कुलर वेरिएंट निकालने और यह समझाने के लिए कहते हैं कि सभी ऋणात्मक तत्वों वाली ऐरे आँख मूंदकर total - minSum का उपयोग क्यों नहीं कर सकती है।
साक्षात्कारकर्ता क्या जांचता है
- उत्तर को नॉन-रैपिंग और रैपिंग रेंज में विभाजित करना।
- ऐरे को डुप्लिकेट करने के बजाय अधिकतम और न्यूनतम सबएरे योगों के बीच पूरक (complement) का उपयोग करना।
- सभी ऋणात्मक, एक-तत्व वाले और सीमित-पूर्णांक इनपुट के लिए गैर-रिक्त प्रतिबंध को बनाए रखना।
उत्तर देने से पहले स्पष्टीकरण संबंधी प्रश्न
- क्या सबएरे का गैर-रिक्त होना आवश्यक है? हाँ, इसलिए सभी ऋणात्मक इनपुट अपना सबसे बड़ा ऋणात्मक मान लौटाता है।
- क्या एक स्थिति का दो बार उपयोग किया जा सकता है? नहीं; एक रैपिंग रेंज एक गैर-रिक्त मध्य रेंज का पूरक होती है।
- क्या हम केवल योग लौटाते हैं या सीमाएं (indices) भी? यह प्रश्न योग पूछता है; सीमाओं के लिए अतिरिक्त इंडेक्स प्रबंधन और एक सर्कुलर निरूपण की आवश्यकता होती है।
30-सेकंड उत्तर ढांचा
मैं उत्तर को दो मामलों में विभाजित करता हूँ। एक नॉन-रैपिंग रेंज साधारण अधिकतम सबएरे योग है। एक रैपिंग रेंज कुल योग में से एक गैर-रिक्त न्यूनतम सबएरे योग को घटाने के बराबर होती है। एक ही पास में अधिकतम, न्यूनतम और कुल योग बनाए रखे जाते हैं। यदि न्यूनतम रेंज संपूर्ण ऐरे है, तो पूरक रिक्त होता है, इसलिए मैं इसके बजाय साधारण अधिकतम मान लौटाता हूँ। एल्गोरिथ्म का समय O(n) और अतिरिक्त स्थान O(1) है।
चरण-दर-चरण गहन विश्लेषण
1. दो मामलों को निकालना
Kadane's algorithm सर्वश्रेष्ठ नॉन-रैपिंग रेंज ढूंढता है। एक रैपिंग रेंज में एक प्रत्यय (suffix) और उपसर्ग (prefix) शामिल होते हैं; इसका पूरक एक गैर-रिक्त निरंतर मध्य रेंज है, इसलिए इसका योग total - minSubarray है। इन उम्मीदवारों में से बड़ा मान लेने से प्रत्येक मान्य रेंज शामिल हो जाती है।
2. Kadane इनवेरिएंट्स को बनाए रखना
मान x पर, साधारण स्थिति वर्तमान स्थिति पर समाप्त होने वाले सर्वश्रेष्ठ योग को संग्रहीत करती है; न्यूनतम स्थिति वहां समाप्त होने वाले सबसे छोटे योग को संग्रहीत करती है। पिछली वर्तमान स्थिति से प्रत्येक को अपडेट करें, फिर वैश्विक चरम सीमाओं (global extrema) को अपडेट करें। वैश्विक अधिकतम को ऋणात्मक अनंत और न्यूनतम को धनात्मक अनंत पर प्रारंभ करें ताकि एक-तत्व वाली ऋणात्मक ऐरे को रिक्त न माना जाए।
3. सभी ऋणात्मक इनपुट को संभालना
जब प्रत्येक मान ऋणात्मक होता है, तो न्यूनतम सबएरे संपूर्ण ऐरे होता है और total - minSubarray शून्य होता है, जो एक रिक्त रेंज का प्रतिनिधित्व करता है और प्रश्न के नियमों का उल्लंघन करता है। जब भी सर्वश्रेष्ठ योग ऋणात्मक हो, साधारण अधिकतम मान लौटाएं। न्यूनतम रेंज पूरी ऐरे को कवर करती है या नहीं, इसे ट्रैक करना एक अन्य मान्य कार्यान्वयन है, लेकिन चिह्न (sign) की जांच करना अधिक सरल है।
4. कोड और जटिलता
from typing import List
class Solution:
def maxSubarraySumCircular(self, nums: List[int]) -> int:
total = 0
current_max = current_min = 0
best_max = float("-inf")
best_min = float("inf")
for value in nums:
total += value
current_max = max(value, current_max + value)
best_max = max(best_max, current_max)
current_min = min(value, current_min + value)
best_min = min(best_min, current_min)
if best_max < 0:
return int(best_max)
return int(max(best_max, total - best_min))प्रत्येक तत्व को एक बार देखा जाता है: O(n) समय और O(1) अतिरिक्त स्थान। जब भाषा का मशीन पूर्णांक कुल या मध्यवर्ती योगों के लिए ओवरफ्लो हो सकता है, तो एक व्यापक पूर्णांक प्रकार (wider integer type) का उपयोग करें।
5. प्रति-उदाहरण और सत्यापन
[5,-3,5] का रैपिंग उत्तर 5 + 5 = 10 है। [-3,-2,-3] को -2 लौटाना चाहिए, शून्य नहीं। [1,-2,3,-2] के लिए, साधारण उत्तर 3 है और रैपिंग उम्मीदवार इससे अधिक नहीं हो सकता। परीक्षणों में एक तत्व, सभी धनात्मक इनपुट, संपूर्ण सर्कुलर ऐरे के समतुल्य एक सीमा और पूर्णांक सीमा के करीब के योग भी शामिल होने चाहिए।
उच्च गुणवत्ता वाला नमूना उत्तर
“मैं पहले उन सीमाओं को अलग करता हूँ जो छोर पार करती हैं और जो नहीं करती हैं। नॉन-रैपिंग मामला Kadane का अधिकतम है। एक रैपिंग रेंज कुल ऐरे योग में से एक गैर-रिक्त न्यूनतम मध्य रेंज घटाकर प्राप्त होती है, इसलिए मैं एक ही पास में अधिकतम और न्यूनतम Kadane स्थितियों को बनाए रखता हूँ। यदि प्रत्येक मान ऋणात्मक है, तो न्यूनतम रेंज संपूर्ण ऐरे होती है और इसका पूरक रिक्त होता है, इसलिए मैं साधारण अधिकतम लौटाता हूँ। यह O(n) समय और O(1) स्थान लेता है, जिसमें एक मान, सभी ऋणात्मक, रैपिंग धनात्मक और पूर्णांक सीमाओं के लिए परीक्षण शामिल हैं।”
सामान्य गलतियाँ
- डुप्लिकेट ऐरे पर सामान्य Kadane चलाना → एक स्थिति का दो बार उपयोग हो सकता है → विंडो को सीमित करें या पूरक मामला निकालें।
- हमेशा
total - minSumलौटाना → सभी ऋणात्मक इनपुट शून्य (रिक्त रेंज) उत्पन्न करते हैं → पहले ऋणात्मक-सर्वश्रेष्ठ शाखा को संभालें। - एक रिक्त न्यूनतम रेंज की अनुमति देना → पूरक सूत्र गैर-रिक्त प्रतिबंध खो देता है → न्यूनतम Kadane को वास्तविक तत्व से प्रारंभ करें।
- बिना इनवेरिएंट्स के O(n) का दावा करना → सीमा मामलों का कवरेज अप्रमाणित रहता है → दोनों रेंज मामलों और प्रत्येक स्थिति को परिभाषित करें।
अनुवर्ती प्रश्न और उत्तर
आप प्रारंभ और अंत स्थितियों को कैसे लौटाएंगे?
अधिकतम और न्यूनतम दोनों स्थितियों के लिए सीमाओं को रिकॉर्ड करें। एक रैपिंग उत्तर न्यूनतम रेंज का पूरक है, जिसे [minEnd+1,n-1] और [0,minStart-1] के रूप में दर्शाया जाता है; परिभाषित करें कि क्या API दो रैखिक टुकड़े लौटाता है या एक सर्कुलर शुरुआत और लंबाई।
यदि रिक्त सबएरे की अनुमति होती तो कोड कैसे बदलता?
उत्तर कम से कम शून्य होगा, इसलिए वर्तमान योग शून्य पर रीसेट हो सकता है। यह सभी ऋणात्मक मामलों के सिमेंटिक्स को बदल देता है; रिक्त-अनुमत Kadane वेरिएंट का उपयोग करने से पहले प्रश्न की पुष्टि करें।
क्या आप डायनामिक स्ट्रीम के लिए O(1) में उत्तर अपडेट कर सकते हैं?
एक छोर पर जोड़ना प्रीफिक्स, सफिक्स और सारांश मान बनाए रख सकता है, लेकिन किसी भी पुराने तत्व को हटाने से चरम मान अमान्य हो जाते हैं। एक सेगमेंट ट्री या ब्लॉक सारांश की आवश्यकता हो सकती है। अपडेट की दिशा, क्वेरी दर और क्या सन्निकटन (approximation) की अनुमति है, इसे स्पष्ट करें।
क्या होगा यदि सबएरे की लंबाई ठीक k होनी चाहिए?
पूरक सूत्र अब लागू नहीं होता है क्योंकि पूरक की लंबाई बाधित होती है। ऐरे को लंबाई-2n अनुक्रम के रूप में मानें, प्रीफिक्स सम या एक deque के साथ लंबाई-k विंडो बनाए रखें, और विंडो को n पर सीमित करें; जटिलता क्वेरी पैटर्न पर निर्भर करती है।