Interview Question: Maximum Subarray Sum C++

Company Interviews Using C++ Data Structures and Algorithms

long long maxSubarraySum(vector<int> arr, int n)
{
    long long maxSoFar = 0;
    long long currentSum = 0;
    for(int i =0; i<n; i++){
        currentSum+=arr[i];
        if(currentSum>maxSoFar){
            maxSoFar = currentSum;
        }
        if(currentSum<0){
            currentSum =0;
        }
    }
    return maxSoFar;
}

English :

This C++ code defines a function called `maxSubarraySum` that takes in two parameters: a vector of integers `arr` and an integer `n`, representing the size of the array. The function’s purpose is to find the maximum sum of a subarray within the given array.

Here’s a step-by-step explanation of how the code works:

1. `long long maxSoFar = 0;` and `long long currentSum = 0;`: Two variables are initialized, `maxSoFar` and `currentSum`, both of type `long long`. `maxSoFar` will keep track of the maximum subarray sum found so far, and `currentSum` will keep track of the sum of the current subarray being examined.

2. The code then enters a `for` loop that iterates through the elements of the input array `arr`.

3. `currentSum += arr[i];`: For each iteration of the loop, the current element in the array `arr` is added to the `currentSum`. This effectively builds a subarray sum by summing up consecutive elements in the array.

4. `if (currentSum > maxSoFar) { maxSoFar = currentSum; }`: This condition checks if the `currentSum` is greater than the `maxSoFar`. If it is, it updates `maxSoFar` to the value of `currentSum`. This means that the code keeps track of the maximum subarray sum encountered so far.

5. `if (currentSum < 0) { currentSum = 0; }`: This condition checks if the `currentSum` becomes negative. If it does, it means that the subarray’s sum should be reset to zero since including a negative sum would only decrease the overall sum. This step is crucial for finding the maximum subarray sum since it allows the algorithm to consider starting a new subarray whenever the current subarray’s sum becomes negative.

6. The loop continues to the next element in the array, and steps 3–5 are repeated until all elements in the array have been processed.

7. After the loop finishes, the function returns the `maxSoFar` variable, which holds the maximum subarray sum found in the input array.

In summary, this code implements the Kadane’s algorithm for finding the maximum subarray sum in a given array. It keeps track of the maximum subarray sum found so far and resets the current subarray sum to zero whenever it becomes negative. This approach ensures that the algorithm considers all possible subarrays and efficiently finds the maximum subarray sum.

Hindi :

यह C++ कोड एक फ़ंक्शन `maxSubarraySum` को परिभाषित करता है जो दो पैरामीटर लेता है: एक पूर्णांकों का वेक्टर `arr` और एक पूर्णांक `n`, जो वेक्टर का आकार प्रस्तुत करता है। इस फ़ंक्शन का उद्देश्य दिए गए वेक्टर में एक उप-वर्ग की अधिकतम योग की खोज करना है।

यहाँ कोड काम करने की कदम-से-कदम व्याख्या है:

1. `long long maxSoFar = 0;` और `long long currentSum = 0;`: दो चर `maxSoFar` और `currentSum` को आरंभित किया जाता है, दोनों के प्रकार `long long` हैं। `maxSoFar` वर्तमान तक पाए जाने वाले अधिकतम उप-वर्ग योग का पता रखेगा, और `currentSum` वर्तमान उप-वर्ग के योग का पता रखेगा जिसे जांच रहा है।

2. उसके बाद कोड एक `for` लूप में प्रवेश करता है जो प्रायोजन वेक्टर `arr` के तत्वों में फेरी करता है।

3. `currentSum += arr[i];`: प्रत्येक लूप के प्रतिस्थान पर, वेक्टर `arr` में वर्तमान तत्व को `currentSum` में जोड़ा जाता है। यह वास्तव में वेक्टर में लगभग तत्वों को जोड़कर एक उप-वर्ग योग बनाता है।

4. `if (currentSum > maxSoFar) { maxSoFar = currentSum; }`: यह शर्त यह जाँचती है कि क्या `currentSum` `maxSoFar` से अधिक है। यदि हां, तो यह `maxSoFar` को `currentSum` के मूल्य पर अद्यतित करती है। इसका मतलब है कि कोड वर्तमान तक पाए गए अधिकतम उप-वर्ग योग का पता रखता है।

5. `if (currentSum < 0) { currentSum = 0; }`: यह शर्त यह जाँचती है कि क्या `currentSum` नकारात्मक हो गया है। अगर ऐसा है, तो इसका मतलब है कि उप-वर्ग के योग को शून्य पर रीसेट करना चाहिए क्योंकि एक नकारात्मक योग शीर्षक योग को कम करने के सिवाय कुछ नहीं करेगा। इस कदम को अधिकतम उप-वर्ग योग की खोज के लिए महत्वपूर्ण है क्योंकि इससे यह सुनिश्चित होता है कि एल्गोरिदम वर्तमान उप-वर्ग के योग नकारात्मक होने पर नए उप-वर्ग की शुरुआत को विचार करे।

6. लूप वेक्टर में अगले तत्व पर बढ़ता है, और कदम 3–5 को दोहराता है जब तक वेक्टर के सभी तत्व प्रसंस्कृत नहीं किए जाते हैं।

7. जब लूप समाप्त होता है, फ़ंक्शन `maxSoFar` चर को लौटाता है, जिसमें प्राय

वेक्टर में पाए गए अधिकतम उप-वर्ग योग होता है।

संक्षेप में, यह कोड दिए गए वेक्टर में अधिकतम उप-वर्ग योग खोजने के लिए कदने के एल्गोरिदम को प्राप्त करने के लिए है। यह सुनिश्चित करता है कि वर्तमान तक पाए गए अधिकतम उप-वर्ग योग का पता रखता है और जब वर्तमान उप-वर्ग का योग नकारात्मक होता है, तो इसे शून्य पर रीसेट करता है। इस दृष्टिकोण से यह एल्गोरिदम सभी संभावित उप-वर्गों का विचार करता है और अधिकतम उप-वर्ग योग को प्राप्त करने के लिए कुशलता से काम करता है।

Hinglish :

Yeh C++ code ek function ko define karta hai jise `maxSubarraySum` ke naam se pukara gaya hai. Ismein do parameters hain: ek integer vector `arr` aur ek integer `n`, jo array ki size ko represent karta hai. Is function ka maksad di gayi array ke andar se subarray ki maximum sum nikalna hai.

Yahaan ek kadam-se-kadam samjhane ki koshish karte hain ki yeh code kis tarah kaam karta hai:

1. `long long maxSoFar = 0;` aur `long long currentSum = 0;`: Do variables ko shuruaat mein initialize kiya gaya hai, `maxSoFar` aur `currentSum`, dono `long long` data type ke hain. `maxSoFar` current tak ki maximum subarray sum ko track karega, aur `currentSum` current subarray ke sum ko track karega jo abhi examine kiya ja raha hai.

2. Fir code ek `for` loop mein enter hota hai jo input array `arr` ke elements par iterate karta hai.

3. `currentSum += arr[i];`: Har iteration mein, current element ko array `arr` mein `currentSum` ke saath joda jata hai. Isse effectively subarray ke sum ko build kiya jata hai, array ke consecutive elements ko jodkar.

4. `if (currentSum > maxSoFar) { maxSoFar = currentSum; }`: Is shart se check kiya jata hai ki kya `currentSum` `maxSoFar` se bada hai. Agar hai, to `maxSoFar` ko `currentSum` ke value se update kiya jata hai. Iska matlab hai ki code current tak ki maximum subarray sum ko track karta hai.

5. `if (currentSum < 0) { currentSum = 0; }`: Is shart se dekha jata hai ki kya `currentSum` negative ho gaya hai. Agar ho gaya, to iska matlab hai ki subarray ka sum zero par reset karna chahiye, kyunki negative sum ko shamil karne se overall sum sirf ghat jayega. Yeh kadam maximum subarray sum dhoondhne ke liye mahatvapurn hai, kyunki yeh algorithm current subarray ke sum negative ho jata hai, to naye subarray ko shuru karne ka vichar kare.

6. Loop agli array element tak jata hai, aur kadam 3–5 dobara kiye jate hain jab tak array ke sabhi elements ko process na kiya jaye.

7. Jab loop samapt hota hai, to function `maxSoFar` variable ko return karta hai, jo input array mein paya gaya maximum subarray sum ko hold karta hai.

Saransh mein, yeh code di gayi array mein maximum subarray sum dhoondhne ke liye Kadane’s algorithm ko implement karta hai. Ismein maximum subarray sum ko track kiya jata hai aur current subarray sum ko reset kiya jata hai jab yeh negative ho jata hai. Yeh approach yeh surakshit karta hai ki algorithm sabhi sambhav subarrays ko vichar kare aur maximum subarray sum ko prabhavi tarike se dhoondhe.