So I stumbled upon this code when trying to find the best way to obtain the max subsequence (mss).

It works like it's supposed to and does indeed find the max subsequence. But I am a little confused as to how it works. The part that confuses me is when it calls the function on itselfCode:int mss(int* a, int left, int right){ // If the array is a one element array, compare with 0 if (left == right){ return a[left] > 0 ? a[left] : 0; } int mid = ((left + right) / 2); // Midpoint int maxLeftSum = mss(a, left, mid); // Left of midpoint int maxRightSum = mss(a, (mid+1), right); // Right of midpoint // Set variables = 0 for left and right of mipoint sums int maxLeftCount = 0, leftCount = 0; int maxRightCount = 0, rightCount = 0; // Left of midpoint for (int i = mid; i >= left; i--){ leftCount += a[i]; if (leftCount > maxLeftCount) maxLeftCount = leftCount; } // Right of midpoint for (int i = (mid+1); i <= right; i++){ rightCount += a[i]; if (rightCount > maxRightCount) maxRightCount = rightCount; } // Find max of the three values int max = maxLeftSum; if (maxRightSum > max) max = maxRightSum; if (maxRightCount + maxLeftCount > max) max = (maxRightCount + maxLeftCount); return max; }

It seems that this would continue to loop until there is only one element in which it would compare it with 0 and return the largest value. Once that is returned, it continues with the code to the for loops. The first time it would simple return the first element in the array for left, and the second for right.Code:int maxLeftSum = mss(a, left, mid);

Then it walks its way out, each time the for loops get larger and larger. But I don't understand how this helps with the left and right sections.

I guess the jist of this whole thing is that I wouldn't (at this current moment in time) be able to write this by myself because I don't know exactly how it works. Can someone shed some light for me?