Thread: Help with Searching Array for Longest Sequence of an Element

  1. #1
    Registered User w2look's Avatar
    Join Date
    Nov 2008
    Posts
    31

    Help with Searching Array for Longest Sequence of an Element

    Hi,

    I'm new to the forum and I need some help.
    My task is to write a program which defines a function to search through a fixed size
    array of integers and count the longest sequence (consecutive repetition) of a specific
    element in the array. The array and the search element are to be passed as a parameter
    to the function and the longest repetition is the result.

    For example:

    If the following array of 10 integers is input by the user:

    1 1 2 2 3 1 1 1 2 3

    and the element that you want to find the longest sequence of is 1,
    then the program should return the number 3 as the answer.
    (because the most consecutive repetitions of 1 in the array at any given point is 3)

    I have finished the code to greet, prompt and receive the input from the user, store the
    input into an array and execute a print statement for the answer. All of the for loops and
    while loops are written including an exit value for when the user would like to quit. I have
    created the function, declared the function prototypes and have the proper variables
    being passed between the function and main.

    However, I am having trouble getting my function to work. I am not sure how to correctly
    go about writing the code for the actual searching of the array elements.

    I know I need to look at each element separately.
    I don't know how to put that into code.

    I know I need to then determine if it is equal to the following element in the array.
    I don't know how to put that into code.

    I know that if it is equal to the next element then I should increment a counter by one to
    count how many times it repeats and when the program hits a new number, the value in
    the counter should be stored into a new array that will contain the values of the length
    of each consecutive repeated number.
    I don't know how to put that into code.

    Once I have the array containing the lengths of the repetitions, I know how to write the
    code to find the max value in that array and print it, but getting to that point is my problem.

    If anyone has any suggestions as to how I should begin to code this function,
    I would greatly appreciate your help.

    .

  2. #2
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    There is a book called Algorithms by Kneuth (i think that is the title of the book and the author... idk... to be honest I am just trying to shirk my spanish homework at the moment). It has some really good methodology to use.

  3. #3
    Registered User
    Join Date
    Sep 2008
    Posts
    58
    This reminds me of maximum sum subvector problem I had to do. For this you can just do, if(A[i] == 1 && A[i -1] == 1), the count would go up. Then that count would be initialized to some variable, I am calling it highest. Then check to see if the count goes over the highest, and if it does it will initialize it to highest. So then your function would return the variable highest.

    Hope that made sense.

    This link is for that problem. See the similarities?
    Last edited by blurx; 11-19-2008 at 09:15 PM.

  4. #4
    Registered User w2look's Avatar
    Join Date
    Nov 2008
    Posts
    31
    Quote Originally Posted by blurx View Post
    For this you can just do, if(A[i] == 1 && A[i -1] == 1), the count would go up. Then that count would be initialized to some variable, I am calling it highest. Then check to see if the count goes over the highest, and if it does it will initialize it to highest. So then your function would return the variable highest.
    Thanks blurx, but I'm not sure that will work for this problem.

    I don't need to check if A[i] == 1

    but it gives me an idea! AND possibly changed how I was thinking about this problem!

    I think what I need to check is if A[i] == " number to be checked" then ++counter

    I'm still not sure how to store the value of the counter and then reset the counter to 0,
    so I can check to see if it is larger than the next value I create by checking the next sequence.

    for instance, in the array I mentioned earlier, the program would check if the first element
    of the array was equal to the number to be checked (1). Since it is, it would return a "true"
    result and add 1 to the counter.

    Then, the program should check to see if the 3rd element is equal to the number to be checked.
    In this case, the 3rd element is 2 so it would return a "false" result.
    At this point I need to store the value of the counter
    (which is 2 for the length of the repeating sequence of 1's) and reset the counter.

    Then I need to check if the 4th element of the array is equal to the number to be checked (1).
    If it is, add one to the counter and check to see if the 5th is the same and so on.

    Whenever the sequence terminates (the next element in the array is not the number being checked)
    the program should check the value in the counter against it's previous value. If the new counter value
    is larger than the previously stored value, it should be overwritten.

    Once it has checked the entire array, it can then return the last value stored which should be the largest.

    from my example, given the array

    1 1 2 2 3 1 1 1 2 3

    the program should check this array one element at a time until it finds the number to be checked (1)

    when it finds the number(1), it should add one to the counter. It should then check to see if the next element is (1).
    If so, it should add one to the counter. If not, the value of the counter at this point should be stored in a variable
    and the counter should be reset to zero. The program should then continue checking the array from the spot it left
    off, until it finds the number (1) again. When it does, it should add one to the counter, and so on.

    Once it has checked the entire array, then it should return the final value stored in the variable.

    I know exactly what I want to do, I just don't know the syntax or proper coding
    structure to get it done.

    If you or anyone else has more suggestions, I'm all ears.
    Last edited by w2look; 11-19-2008 at 10:36 PM. Reason: mistaken course of action

  5. #5
    HelpingYouHelpUsHelpUsAll
    Join Date
    Dec 2007
    Location
    In your nightmares
    Posts
    223
    This should work (code tags to keep indentation):
    Code:
    1. Read the number in to be searched for
    2. Iterate through the list
           - If number to be checked is found, increment counter
           - If number found is not the number being looked for and counter > 0:
                 - Store the counter in a seperate array of ints
                 - Reset counter
    3. If the array of ints is empty return 0
    4. Perform a linear search on the seperate array to find largest element
    5. Return largest value
    Hope this helps, there might be quicker ways but you need something to get started before thinking of optimisation.
    Last edited by P4R4N01D; 11-19-2008 at 11:31 PM. Reason: Added CODE tags
    long time no C; //seige
    You miss 100% of the people you don't C;
    Code:
    if (language != LANG_C && language != LANG_CPP)
        drown(language);

  6. #6
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    The standard way to iterate through an array is:

    Code:
    for(i = 0; i < sizeOfArray; i++)  {
       //whatever code you need here.
       if(Array[i] == numberYouWant)
          count++;
    }
    /* then maybe something like this */
    if(count > longestSequence)
       longestSequence = count;
    Post up your code so we can see what you're trying. If it's pseudo code, that's fine, also.

  7. #7
    Registered User w2look's Avatar
    Join Date
    Nov 2008
    Posts
    31

    Thanks Everyone

    I just wanted to thank everyone for posting their suggestions.

    I have figured it out with your help and working through the problem.

  8. #8
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Ya know, a simplification of the Boyer-Moore string matching algorithm, but operating on an array of integers instead of characters would seem like an efficient idea for this.
    Okay, what I mean is, after finding a sequence of length n, as you continue through the rest of the array, you may as well step by n each time, unless you hit the number you are looking for. I.e Once you've found a sequence of length n, there's no point in looking for anything but a sequence of length n+1 or greater.

    That is all of course if your array is long enough to warrant something smarter than the obvious simple method.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. 2d array question
    By gmanUK in forum C Programming
    Replies: 2
    Last Post: 04-21-2006, 12:20 PM
  2. question about multidimensional arrays
    By richdb in forum C Programming
    Replies: 22
    Last Post: 02-26-2006, 09:51 AM
  3. Deleting element from an array problem
    By xamlit in forum C Programming
    Replies: 5
    Last Post: 12-03-2005, 04:53 PM
  4. Trying to create a 5 element integer array
    By nadeni0119 in forum C++ Programming
    Replies: 5
    Last Post: 03-26-2003, 08:35 PM
  5. Hi, could someone help me with arrays?
    By goodn in forum C Programming
    Replies: 20
    Last Post: 10-18-2001, 09:48 AM

Tags for this Thread