Thread: Help Code Is Not Working

  1. #1
    Registered User
    Join Date
    Oct 2008
    Posts
    13

    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);
    }

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    And "not working" means what, exactly?

  3. #3
    Registered User
    Join Date
    Oct 2008
    Posts
    13

    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
    thanks for replying

  4. #4
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    I would guess because printReverse does not print the first element of the array.

  5. #5
    Registered User
    Join Date
    Oct 2008
    Posts
    13
    yes but dont know how to debug the code
    any suggestions that u can give

  6. #6
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    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).
    Last edited by tabstop; 11-10-2008 at 10:32 AM.

  7. #7
    Registered User
    Join Date
    Oct 2008
    Posts
    13
    i am sorry not able to get you
    can u plz send me a sample code snippet

  8. #8
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by srivatsan View Post
    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.

  9. #9
    Registered User
    Join Date
    Oct 2008
    Posts
    13
    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);
    }

  10. #10
    Registered User
    Join Date
    Oct 2008
    Posts
    13
    there is no other way other than calling the
    function recursively

  11. #11
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by srivatsan View Post
    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."

  12. #12
    Registered User
    Join Date
    Oct 2008
    Posts
    13
    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

  13. #13
    Registered User
    Join Date
    Oct 2008
    Posts
    13
    i tried by replacing
    if (curr == 0) return ;
    with
    if (curr < 0) return ;
    but still i am not getting the correct answer

  14. #14
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    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.

  15. #15
    Registered User
    Join Date
    Dec 2007
    Posts
    214
    Quote Originally Posted by tabstop View Post
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Code not working?
    By Elysia in forum C++ Programming
    Replies: 12
    Last Post: 04-06-2009, 01:57 AM
  2. Replies: 3
    Last Post: 02-24-2009, 08:49 PM
  3. C code not working
    By D3ciph3r in forum C Programming
    Replies: 2
    Last Post: 05-27-2005, 04:13 PM
  4. Trying to eject D drive using code, but not working... :(
    By snowfrog in forum C++ Programming
    Replies: 3
    Last Post: 05-07-2005, 07:47 PM
  5. Linked List Working Code
    By Linette in forum C++ Programming
    Replies: 9
    Last Post: 01-24-2002, 12:00 PM