Max SubSequence using recursion

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

Code:

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 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 itself

Code:

int maxLeftSum = mss(a, left, mid);

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.

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?

Originally Posted by Amoxaphobic

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.

Because it branches into two each time:

Code:

original call -> left -> left -> left
                                     -> right
                           -> right -> left
                                       -> right
                -> right -> left -> left
                                      -> right
                           -> right -> left
                                       -> right

When the calls return, each previous call has a value set for maxRightSum and maxLeftSum.

You'll probably get some insights into the mechanics if you throw some appropriate "cout" in.

Thanks for the reply.
That helps, but let me see if I understand this...

The code will run the for loops for every two elements (the call on itself will eventually lead to two elements which are then split for left and right). If the code runs down to one element, it simply returns the largest of that element or 0. It recursively adds the elements from left and right respectively, each time comparing with the previously saved number to see which is larger. If the comparative is larger, it replaces to the current largest value.

At the end, it will add the largest sum from left and largest sum from right and compare that value with the three (largest left, largest right, largest combined) to see which is the largest value. The largest value will be the max subsequence?

Is that correct?

Originally Posted by Amoxaphobic

Is that correct?

That's what it looks like, yep, and it seems like a clever/elegant solution IMO. Perhaps not the most efficient tho (just a guess).

Try following the algorithm by applying it yourself on paper with a small simple array. Basically it breaks down the array into smaller and smaller subsequences and weighs them against one another in a kind of round robin elimination; the winner from each comparison (or the combination of both, if they are both positive) works its way up.

Cool. Thank you so much for your help!