classSolution{public:intmaxSubarraySumCircular(vector<int>&nums){intn=nums.size();intmaxSum=INT_MIN;// We initialize it with INT_MIN so that any subarray sum will be larger and can replace it// This outer loop iterates through each possible starting index of a subarrayfor(inti=0;i<n;i++){// We reuse it in the inner loop to avoid recalculating from scratchintcurrSum=0;// This inner loop grows the subarray one element at a time, wrapping around the end using modulofor(intj=0;j<n;j++){// We use modulo to wrap around the circular arrayintindex=(i+j)%n;// Add the current element to the running sumcurrSum+=nums[index];// Update maxSum if the current running sum is greatermaxSum=max(maxSum,currSum);}}returnmaxSum;}};
classSolution{public:intmaxSubarraySumCircular(vector<int>&nums){intn=nums.size();// (Case 1) To find the maximum sum of a NORMAL subarray (Kadane's Algorithm)// maxSum stores the answer for the non-circular case// currentMax tracks the max sum of a subarray ending at the current positionintmaxSum=nums[0];intcurrentMax=nums[0];// (Case 2) To find the minimum sum of a NORMAL subarray. We'll use this to// calculate the maximum circular sum// minSum stores the minimum sum found so far// currentMin tracks the min sum of a subarray ending at the current positionintminSum=nums[0];intcurrentMin=nums[0];// (Case 2) We also need the total sum of all numbers in the arrayinttotalSum=nums[0];// We loop from the second element (index 1) because we've already used the first// element to initialize our variablesfor(inti=1;i<n;++i){intnum=nums[i];// --- Part 1: Kadane's algorithm for the maximum sum ---// At each step, we either start a new subarray with the current number,// or we add the current number to our existing subarray. We do whichever is largercurrentMax=max(num,currentMax+num);maxSum=max(maxSum,currentMax);// --- Part 2: Kadane's algorithm for the minimum sum ---// This is the same logic, but for the minimum. We either start a new// subarray or continue the old one, doing whichever is smaller.currentMin=min(num,currentMin+num);minSum=min(minSum,currentMin);// --- Part 3: Calculate the total sum ---totalSum+=num;}// This is our critical edge case check. If maxSum is negative, it means all numbers// in the array are negative. In this case, the circular sum (total - min) would be incorrect// So, the answer must be the non-circular max sumif(maxSum<0){returnmaxSum;}// If we pass the check, the answer is the larger of the two cases:// 1. The normal max subarray sum (maxSum)// 2. The wrapping max subarray sum (totalSum - minSum)returnmax(maxSum,totalSum-minSum);}};
Warning
LINK
You are about to visit a link which has been flagged with the above content warnings. Do you wish to continue?