Help Code Is Not Working

Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last
• 11-10-2008
srivatsan
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); }```
• 11-10-2008
tabstop
And "not working" means what, exactly?
• 11-10-2008
srivatsan
I am Not Getting the Proper OUT PUT
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
• 11-10-2008
tabstop
I would guess because printReverse does not print the first element of the array.
• 11-10-2008
srivatsan
yes but dont know how to debug the code
any suggestions that u can give
• 11-10-2008
tabstop
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).
• 11-10-2008
srivatsan
i am sorry not able to get you
can u plz send me a sample code snippet
• 11-10-2008
tabstop
Quote:

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.
• 11-10-2008
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

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); }```
• 11-10-2008
srivatsan
there is no other way other than calling the
function recursively
• 11-10-2008
tabstop
Quote:

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."
• 11-10-2008
srivatsan
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
• 11-10-2008
srivatsan
i tried by replacing
if (curr == 0) return ;
with
if (curr < 0) return ;
but still i am not getting the correct answer
• 11-10-2008
tabstop
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.
• 11-10-2008
DaveH
Quote:

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.
Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last