Help Code Is Not Working

i got the code for this problem but not able to find where i am wrong
my problem is as follows

Given an array of numbers, find the longest subsequence whose elements grow monotonically:
1 4 8 2 5 7 3 6 => 1 4 5 7
1 4 8 2 5 7 3 6 7 => 1 4 5 6 7
1 4 8 2 3 7 4 6 => 1 2 3 4 6
that is we must form subsets and find which is longest among them
as showed in the above example

Code:

#include<iostream.h>
#include<conio.h>

int maxRank (int curr, int* arr, int* rank) {
    int max = 0 ;
    for (int i = 0; i <= curr; i++) {
        if (arr[i]<arr[curr] && rank[i]>rank[max]) {
            max = i ;
        }
    }

    return max ;
}

void printReverse (int curr, int* arr, int* back) {
    if (curr == 0) return ;
    printReverse (back[curr], arr, back) ;
    cout << arr[curr] << " " ;
}

void longestMonotoneSubsequence (int count, int* arr) {
    int* back = new int[count] ;
    int* rank = new int[count] ;
    int max = 0 ;
    rank[0] = 0, back[0] = 0 ;
    for (int i = 0; i <= count; i++) {
        back[i] = maxRank (i, arr, rank) ;
        rank[i] = rank[back[i]]+1 ;
        if (rank[i] > rank[max]) {
            max = i ;
        }
    }

    printReverse (max, arr, back) ;
    cout << "\n" ;
    delete rank, back ;
}

void main()
{
int n;
int a[100];
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a[i];
}
longestMonotoneSubsequence(n,&a);
}

And "not working" means what, exactly?

suppose if i give
8 as the number of elments
and enter the elements as follows
1 4 8 2 5 7 3 6 => 1 4 5 7
i must get the output as 1 4 5 7
but i get
only 4 5 7
i am not able to find the reason
thanks for replying

I would guess because printReverse does not print the first element of the array.

yes but dont know how to debug the code
any suggestions that u can give

Fix your base case in printReverse so that it prints the entire array, not "the entire array except for the first element". Oh, and change void main to int main while you're there.

Also how did this even compile? Removing conio.h, changing iostream.h to iostream and adding using namespace std, changing void main to int main, I still get this:

Code:

$ g++ -Wall -Wextra -o temp temp.cpp
temp.cpp: In function ‘void longestMonotoneSubsequence(int, int*)’:
temp.cpp:36: warning: right-hand operand of comma has no effect
temp.cpp: In function ‘int main()’:
temp.cpp:48: error: cannot convert ‘int (*)[100]’ to ‘int*’ for argument ‘2’
 to ‘void longestMonotoneSubsequence(int, int*)’

The first warning is for delete back, rank -- that's only a memory leak; the second is the &a in the function call, which as the compiler correctly notes, is not an array, but a pointer to an array.

Once I fix those, and fix the base case of print as mentioned above, I get the correct result (at least for your test case).

i am sorry not able to get you
can u plz send me a sample code snippet

Originally Posted by srivatsan

i am sorry not able to get you
can u plz send me a sample code snippet

Code:

if (curr == 0) return ;

is bad, wrong, and evil, since it means that the first element (arr[0]) never gets printed. You need to still print in this case, but not call the function recursively.

here is my corrected code
but i am not able to get you point

"Fix your base case in printReverse so that it prints the entire array, not "the entire array except for the first element". Oh, and change void main to int main while you're there."

can u just send me the code snippet on how you want me to modify

Code:

#include<iostream.h>
#include<conio.h>
int maxRank (int curr, int* arr, int* rank) {
    int max = 0 ;
    for (int i = 0; i <= curr; i++) {
	if (arr[i]<arr[curr] && rank[i]>rank[max]) {
	    max = i ;
	}
    }

    return max ;
}

void printReverse (int curr, int* arr, int* back) {
    if (curr == 0) return ;
    printReverse (back[curr], arr, back) ;
    cout << arr[curr] << " " ;
}

void longestMonotoneSubsequence (int count, int* arr) {
    int* back = new int[count] ;
    int* rank = new int[count] ;
    int max = 0 ;
    rank[0] = 0, back[0] = 0 ;
    for (int i = 0; i <= count; i++) {
        back[i] = maxRank (i, arr, rank) ;
        rank[i] = rank[back[i]]+1 ;
        if (rank[i] > rank[max]) {
            max = i ;
        }
    }

    printReverse (max, arr, back) ;
    cout << "\n" ;
    delete rank, back ;
}

void main()
{
int n;
int a[100];
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a[i];
}
longestMonotoneSubsequence(n,a);
}

there is no other way other than calling the
function recursively

Originally Posted by srivatsan

here is my corrected code
but i am not able to get you point

"Fix your base case in printReverse so that it prints the entire array, not "the entire array except for the first element". Oh, and change void main to int main while you're there."

can u just send me the code snippet on how you want me to modify

Since the post you responded to had that in it, I would say the answer is "yes". I'm asking you to think for eleven seconds (approximately) about how your printReverse function works. Do so. Trace it out on a piece of paper if you must.

Edit to add: The recursion part is ok, but your base case is wrong. Do the base case correctly, which in this case means "at all, rather than just returning because I don't want to deal with it."

so my recursion is ok
i am looking into it
from the morning i am breaking my head!!!
any way i will try if i dont get plz help me out

i tried by replacing
if (curr == 0) return ;
with
if (curr < 0) return ;
but still i am not getting the correct answer

I don't know what curr would be the next time through, I didn't try it out. When curr==0, you cannot call the function again. Just print it, don't call it again.

Originally Posted by tabstop

Edit to add: The recursion part is ok,

Is it? I might be wrong, its been a long time since I dealt with recursive functions, but the curr value never gets altered, so that function keeps being called with the same parameters. Infinite loop. If I'm missing something, please correct me.