Thread: finding the largest ascending subsequence..

  1. #1
    Banned
    Join Date
    Oct 2008
    Posts
    1,535

    finding the largest ascending subsequence..

    write a function called
    int max_set(int arr[], int size, …………)
    which gets an array of integers
    and returns the length of the longest ascending subsequence.
    you cant use loops or external functions.
    you can add arguments to the signature.

    for example:
    for this array
    arr = 45 1 21 3 33 6 53 9 18
    we can have these subsequences.

    45 53
    1 21 33 53
    1 3 33 53
    1 3 6 53
    1 3 6 9 18
    1 33 53
    1 6 53
    1 6 9 18
    1 53
    1 9 18
    1 18
    21 33 53
    …….
    but the longest is
    1 3 6 9 18
    so it needs to return 5


    i dont know what the algorithm here
    i dont know where to start
    ??

  2. #2
    Banned
    Join Date
    Oct 2008
    Posts
    1,535
    any ideas??

  3. #3
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Where to start would be to figure out the algorithm.

  4. #4
    Banned
    Join Date
    Oct 2008
    Posts
    1,535
    I dont know what is the algorithm here.

    ??

  5. #5
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    So think about it until you figure it out. Can you figure out how to find ascending subsequences? Do you know how to count numbers?

  6. #6
    Banned
    Join Date
    Oct 2008
    Posts
    1,535
    yep
    i need to look for numbers bigger then the current one

    but its a long way till translating into a recursion

  7. #7
    Registered User
    Join Date
    Apr 2008
    Posts
    396
    Turn off your computer, get some paper and a pen and play with some examples until you find a method to solve the problem for any sequence without 'thinking'. Write down this method with words, the translation to a function will be a piece of cake.

  8. #8
    Banned
    Join Date
    Oct 2008
    Posts
    1,535
    i wrote this code that finds the number of members in the ascending sub sequence of the first cell(arr[0]).

    and in that way i could find out the number of objects in every subsequence for evey cell

    but i dont know how to compare each one of the results to find the biggest isnide this function.
    ??

    i am allowed to enter parameters to the signature
    Code:
    #include <stdio.h>
    int max_set(int arr[], int size,int index,int bef);
    int main()
    {
        int array[7] = {9, 1, 3,0,7,10,11};
    
        printf("%d\n",max_set(array,7,0,array[0]));  //number of cells for ascending series of cell 0 
        return 0;
    }
    
    int max_set(int arr[], int size,int index,int bef) 
    {
    	int temp,bigger;
       if (index==size)
       {
         return 1;
       }
       if (arr[index]>bef)
    	    {
         return 1+max_set(arr,size,index+1,arr[index]);
       }
       else
       {
         return max_set(arr,size,index+1,bef);
       }
           
    }//end of function
    Last edited by transgalactic2; 01-13-2009 at 03:22 PM.

  9. #9
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    You don't know how to compare numbers? I usually use "<" and ">" myself.

  10. #10
    Banned
    Join Date
    Oct 2008
    Posts
    1,535
    i dont know how to collect them
    and compare each one of the results
    to determine the biggest
    within this recursive function
    ??

    i can add variables to the signature

  11. #11
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    So you'll need to find the subsequences starting in every cell. You will reasonably necessarily need an array for that.

  12. #12
    Banned
    Join Date
    Oct 2008
    Posts
    1,535
    and how to do that inside a recurtsion

    the recursion itself is built to return only one result for one cell

  13. #13
    Banned
    Join Date
    Oct 2008
    Posts
    1,535
    i think i shouldnt use array but an int variable
    and i will compare each result for the previus cell
    with the current one
    and store the biggest on this variable

    but i dont know how to do that

  14. #14
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by transgalactic2 View Post
    i think i shouldnt use array but an int variable
    and i will compare each result for the previus cell
    with the current one
    and store the biggest on this variable

    but i dont know how to do that
    If you don't know how to do that, how do you write the previous four lines of the post (which is "how to do that")?

  15. #15
    Banned
    Join Date
    Oct 2008
    Posts
    1,535
    but its a plan
    i dont have any idea of how to implement it
    ??

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 22
    Last Post: 05-29-2009, 05:44 PM
  2. Finding the 3 largest numbers of the five entered
    By Bkgrant in forum C Programming
    Replies: 11
    Last Post: 02-13-2009, 01:08 PM
  3. finding the largest number in a binary search
    By Emeighty in forum C++ Programming
    Replies: 20
    Last Post: 07-31-2008, 03:19 AM
  4. Find largest and second largest number (help)
    By Arkon in forum C++ Programming
    Replies: 6
    Last Post: 01-20-2006, 11:21 PM
  5. Finding largest element in array
    By Chaplin27 in forum C++ Programming
    Replies: 2
    Last Post: 04-12-2005, 09:18 PM