maximal value in recursion

Question

Hi, I have this homework assignment:

Let P_i be the element of arr in index i. We say an index i is ‘well-placed’ if there exists an index j (j >= i) so that summing the elements in P_i P_i+1 … P_j yields the index i. In other words, an index is ‘well-placed’ if a sequence of elements beginning at that index yields the index when summed.

We define ‘well-placed length’ of a well-placed index to be j-i+1 – The length of the sequence that when summed shows that the index is well placed. It is possible an index is well-placed with more than a single sequence of elements. The ‘well-placed length’ in that case is the maximal length of the various sequences defining the index as ‘well-placed’. The ‘maximal well-placed length’ is the maximum between the well-placement length of all well-placed indices in arr.

If no index in the array is well-placed, the maximal well-placed length is considered to be zero.

This is the code I wrote (that does not work):

int longestIndexHelper(int arr[], int i, int cur, int sum, int flag)
{
    if((arr[i]==115)||(i<0))
     return 0;
    if((sum==0)&&(flag==0))
     cur= i;
    if((sum+arr[i]==cur)&&(arr[i]<=cur))
     return longestIndexHelper(arr, i+1, i, sum+arr[i], 1)+1;
    else return 0;
}

int longestIndex(int arr[], int length)
{
    int l, h;
    if(length<=0)
     return 0;
    l= longestIndexHelper(arr, length-1, 0, 0, 0);
    h= longestIndexHelper(arr, length, 0, 0, 0);
    if(h>=l)
     return longestIndex(arr, length-1);
    else
     return longestIndex(arr, length-2);
}

I tried to understand why it doesn't return the maximal value, I assume that the IF and ELSE need to define something else to do... I'm allowed only to use these two functions. thank you!

Answer 1

Assume that your longestIndex function finds the 'maximal well-placed length' for a given length parameter. Then it drops it (h and l aren't stored or returned anywhere, are they?), and calls itself with a decreased length. So the function will always return the result of either longestIndex(arr, 0) or longestIndex(arr, -1) which will be always 0.

EDIT: and the longestIndexHelper function can return only 0 too.

Answer 2

The problem seems to be that you need to implement two "loops" via recursion; one is a loop starting at a given index and summing the values as it goes, keeping track of the maximum well placed length for that starting index. The other is a loop trying each possible starting index. I see that your helper function does the former. It seems that you intend the called function to do the latter, but it has no mechanism to keep track of the maximum found so far or the index to check, separate from the length of the input array. To do that, you might want to create another helper function to recurse through all the possible starting indexes. Though I would approach this by expanding the existing helper function to do this also, something like:

int _helper( int arr[], int len, int start, int cur, int sum, int max )
{
    if (start >= len) {
        /* game over, thanks for playing */
        return max;
    } else if (cur >= len) {
        /* try another starting index */
        return _helper( arr, len, start + 1, start + 1, 0, max );
    } else if ( sum + arr[cur] == start && max < cur - start + 1 ) {
        /* found a longer well placed length */
        return _helper( arr, len, start, cur + 1, sum + arr[cur], cur - start + 1 );
    } else {
        /* bzzzt.  try a longer length at this starting index */
        return _helper( arr, len, start, cur + 1, sum + arr[cur], max );
    }
}

int max_well_placed_length( int arr[], int len )
{
    return _helper( arr, len, 0, 0, 0, 0 );
}

#include <stdio.h>

int main(int argc, char **argv) {
    int arr[100];
    int len = 0;
    if (argc > 100) return 1;

    while (--argc) sscanf(*++argv, "%d", &arr[len++]); 

    printf("max well placed length: %d\n", max_well_placed_length(arr, len));
    return 0;
}