Thread: Max SubSequence using recursion

  1. #1
    Registered User
    Join Date
    Oct 2011
    Location
    Siloam Springs, Arkansas, United States
    Posts
    12

    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?

  2. #2
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by Amoxaphobic View Post
    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.
    Last edited by MK27; 11-10-2011 at 02:04 PM.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  3. #3
    Registered User
    Join Date
    Oct 2011
    Location
    Siloam Springs, Arkansas, United States
    Posts
    12
    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?

  4. #4
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by Amoxaphobic View Post
    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.
    Last edited by MK27; 11-10-2011 at 02:46 PM.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  5. #5
    Registered User
    Join Date
    Oct 2011
    Location
    Siloam Springs, Arkansas, United States
    Posts
    12
    Cool. Thank you so much for your help!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. finding the largest ascending subsequence..
    By transgalactic2 in forum C Programming
    Replies: 92
    Last Post: 01-21-2009, 08:57 AM
  2. Minimum Positive Subsequence Sum
    By CrazyNorman in forum C++ Programming
    Replies: 2
    Last Post: 09-11-2008, 04:25 AM
  3. Longest Common Subsequence
    By stimpyzu in forum Tech Board
    Replies: 4
    Last Post: 04-04-2005, 03:18 PM
  4. can someone help me out with recursion
    By JOsephPataki in forum C Programming
    Replies: 10
    Last Post: 05-13-2003, 04:55 PM
  5. help on recursion.
    By indigo0086 in forum C++ Programming
    Replies: 13
    Last Post: 10-24-2002, 02:48 PM