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?