Interview Question | Maximum Subarray| C++
public:
int maxSubArray(vector<int>& nums) {
return maxSubArray(nums, 0, nums.size() - 1);
}
private:
int maxSubArray(vector<int>& nums, int l, int r) {
if (l > r) {
return INT_MIN;
}
int m = l + (r - l) / 2, ml = 0, mr = 0;
int lmax = maxSubArray(nums, l, m - 1);
int rmax = maxSubArray(nums, m + 1, r);
for (int i = m - 1, sum = 0; i >= l; i--) {
sum += nums[i];
ml = max(sum, ml);
}
for (int i = m + 1, sum = 0; i <= r; i++) {
sum += nums[i];
mr = max(sum, mr);
}
return max(max(lmax, rmax), ml + mr + nums[m]);
}English :
This C++ code is an implementation of a well-known algorithm to find the maximum subarray sum in an array using a divide and conquer approach. The algorithm is commonly referred to as “Kadane’s Algorithm.” It efficiently finds the maximum subarray sum by recursively dividing the array into smaller subarrays and then merging the results.
Here’s a breakdown of the code:
1. The `maxSubArray` function is the public interface that users can call. It takes a vector of integers as input and returns the maximum subarray sum.
2. Within the `maxSubArray` function, the private function `maxSubArray` is called with the initial left (l) and right (r) indices of the array. It’s essentially the entry point for the recursive algorithm.
3. The `maxSubArray` private function is where the actual algorithm is implemented.
a. If the left index (l) is greater than the right index (r), this means that the input subarray is empty or invalid. In this case, it returns `INT_MIN`, which represents negative infinity, indicating that there is no valid subarray.
b. The middle index (m) of the current subarray is calculated as the average of the left and right indices.
c. Two variables, `ml` and `mr`, are initialized to 0. These will store the maximum subarray sums in the left and right subarrays.
d. The function then recursively calls itself for two subarrays: the left subarray (`[l, m — 1]`) and the right subarray (`[m + 1, r]`). These recursive calls are responsible for dividing the problem into smaller subproblems.
e. Next, two loops are used to find the maximum subarray sums within the left and right subarrays. The left loop iterates from the middle index (`m — 1`) to the left index (`l`), and the right loop iterates from the middle index (`m + 1`) to the right index (`r`). During these loops, `ml` and `mr` are updated to store the maximum subarray sums in their respective subarrays.
f. Finally, the function returns the maximum value among three possibilities:
— `lmax` and `rmax` (maximum subarray sums in the left and right subarrays)
— `ml + mr + nums[m]` (maximum subarray sum that crosses the middle element)
The code efficiently combines the results from the left and right subarrays and identifies the maximum subarray sum in the entire array. This divide and conquer strategy significantly reduces the time complexity compared to a brute force approach for finding the maximum subarray sum.
Hindi :
यह C++ कोड एक ऐसे प्रस्तावना का हिस्सा है जिसमें एक आरेखित और विजयी तरीके से एक ऐरे में अधिकतम सबऐरे संय प्राप्त करने के लिए एक प्रमुख एल्गोरिथ्म का अंगीकरण किया गया है। इस एल्गोरिथ्म को सामान्यत: “कड़ने का एल्गोरिथ्म” के रूप में व्यापक रूप से जाना जाता है। इसके माध्यम से यह प्राप्त करता है कि अधिकतम सबऐरे की योग्यता के अधिकतम मूल्य को सबऐरों को छोटे अऐरों में विभाजित करके और फिर परिणामों को मिलाकर।
यहाँ इस कोड का एक विवरण है:
1. `maxSubArray` फ़ंक्शन उपयोगकर्ताओं द्वारा कॉल किया जा सकने वाला पब्लिक इंटरफ़ेस है। इसे इनपुट के रूप में एक पूर्णांकों के एक वेक्टर के साथ लिया जाता है और यह अधिकतम सबऐरे संय को लौटाता है।
2. `maxSubArray` फ़ंक्शन के भीतर, प्राइवेट फ़ंक्शन `maxSubArray` को ऐरे के मूल बाएं (l) और दाएं (r) सूचियों के साथ कॉल किया जाता है। यह मूल रूप से पुनर्वर्गीय एल्गोरिथ्म के लिए प्रवेश बिंदु है।
3. `maxSubArray` प्राइवेट फ़ंक्शन में वास्तविक एल्गोरिथ्म का अंगीकरण किया गया है।
a. यदि बायाँ सूचि (l) दाएँ सूची (r) से अधिक है, तो इसका मतलब है कि इनपुट उप-सूची खाली या अमान्य है। इस मामले में, यह `INT_MIN` को लौटाता है, जो नकारात्मक अनंत को प्रस्तुत करता है, जिसका सुझाव है कि कोई वैध सबऐरा नहीं है।
b. वर्तमान उप-सूची के बीच की मध्य सूची (m) उसके बायाँ और दाएँ सूचियों का माध्य सूची के औसत के रूप में गणना की जाती है।
c. दो चरण (ml और mr) को 0 पर प्रारंभ किया जाता है। ये बायाँ और दाएँ सूचियों में अधिकतम सबऐरे संय को संग्रहण करेंगे।
d. इसके बाद, दो सूचियों के लिए खुद को पुनर्वर्गीय रूप से बुलाया जाता है: बायाँ सूची (`[l, m — 1]`) और दाएँ सूची (`[m + 1, r]`)। ये पुनर्वर्गीय कॉल्स बड़ी समस्या को छोटे उप-समस्याओं में विभाजित करने के लिए उत्तरदायक हैं।
और दाएँ सूचियों में अधिकतम सबऐरे संय को खोजने के लिए दो लूपों का उपयोग किया जाता है। बायाँ लूप मध्य सूची (`m — 1`) से बायाँ सूची (`l`) तक घूमता है, और दाएँ लूप मध्य सूची (`m + 1`) से दाएँ सूची (`r`) तक घूमता है। इन लूपों के दौरान, `ml` और `mr` को उनकी संबंधित उप-सूचियों में अधिकतम सबऐरे संय को संग्रहित करने के लिए अपडेट किया जाता है।
f. आखिरकार, फ़ंक्शन तीन संभावनाओं में से अधिकतम मूल्य को लौटाता है:
— `lmax` और `rmax` (बायाँ और दाएँ सूचियों में अधिकतम सबऐरे संय)
— `ml + mr + nums[m]` (मध्य तत्व को छूने वाले अधिकतम सबऐरे संय)
इस कोड में बायाँ और दाएँ सूचियों से परिणामों को संगठित रूप से जोड़ने की क्षमता है और पूरे एरे में अधिकतम सबऐरे संय की पहचान करता है। यह विभाजन और विजयी रणनीति अधिकतम सबऐरे संय प्राप्त करने के लिए एक ब्रूट फ़ोर्स दृष्टिकोण के मुकाबले समय संघटन को संविदानसंगत रूप से कम करता है।
Hinglish :
Yeh C++ ka code ek prasiddh algorithm ki ek vyavastha hai jo ek array mein subarray ki adhik se adhik sum dhundne ke liye ek bhedbhav aur vijayi upay ka istemal karta hai. Is algorithm ko aam taur par “Kadane’s Algorithm” ke roop mein jana jata hai. Yeh code ek array ko chote subarray mein vibhajit karne aur phir un parinamon ko milane ke roop mein adhik se adhik subarray sum dhoondhta hai.
Yahaan code ki vyakhya hai:
1. `maxSubArray` function ek public interface hai jise prayogakarta call kar sakte hain. Isme ek integers vector ko input ke roop mein liya jata hai aur yah sabse adhik subarray sum lauta deta hai.
2. `maxSubArray` function ke bhitar, private function `maxSubArray` ko array ke prarambhik left (l) aur right (r) indices ke saath bulaya jata hai. Yeh mool roop ke liye pravesh bindu hai jahan parantu.
3. `maxSubArray` private function mein vaastavik algorithm ki vyavastha hoti hai.
a. Agar vam index (l) adhik hai, to iska arth hai ki pravesh subarray khali ya anvalid hai. Is avastha mein yah `INT_MIN` lauta deta hai, jo abhaasit aprakash ke roop mein kaarya karta hai aur yah darust subarray nahi hai.
b. Vartaman subarray ke madhya bindu (m) ko vam aur dakshin indices ke madhy ke average ke roop mein ganakar hota hai.
c. Do cariables, `ml` aur `mr`, ko 0 ke barabar prarambh kiya jata hai. Yeh vam aur dakshin subarray mein adhik se adhik subarray sum ko store karenge.
d. Phir, is function ko do subarray ke liye apne aap se punarvritt karne ke liye bulaya jata hai: vam subarray (`[l, m — 1]`) aur dakshin subarray (`[m + 1, r]`). In punarvritt kriyao ki jimmedari badi samasya ko chote sub-samasyao mein vibhajit karne ke liye hoti hai.
e. Agle mein, vam aur dakshin subarray mein adhik se adhik subarray sum dhoondhne ke liye do loop ka istemal hota hai. Vam loop madhya bindu (`m — 1`) se vam bindu (`l`) tak ghumta hai, aur dakshin loop madhya bindu (`m + 1`) se dakshin bindu (`r`) tak ghumta hai. In loopon ke dauraan, `ml` aur `mr` apni samriddh subarrayon mein adhik se adhik subarray sum ko store karne ke liye update hote hain.
f. Ant mein, yah function tin sambhavnaon mein se adhik mahatvapurn mulya lauta deta hai:
— `lmax` aur `rmax` (vam aur dakshin subarrayon mein adhik se adhik subarray sum)
— `ml + mr + nums[m]` (madhya bindu ko laanghne wala adhik se adhik subarray sum)
Yeh code vam aur dakshin subarrayon se aaye parinamon ko sambhalakar poori array mein adhik se adhik subarray sum ko pahchanata hai. Is bhedbhav aur vijayi upay se yah samay complexity ko bhrasht bal upay ke tulna mein bade roop se kam kar deta hai subarray sum dhoondhne ke liye.
