Help with Searching Array for Longest Sequence of an Element

w2look · 11-19-2008, 08:40 PM

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.

.

master5001 · 11-19-2008, 08:41 PM

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.

blurx · 11-19-2008, 09:11 PM

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?

w2look · 11-19-2008, 10:11 PM

Quote:

Originally Posted by blurx

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.

P4R4N01D · 11-19-2008, 11:28 PM

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.

Adak · 11-19-2008, 11:45 PM

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.

w2look · 11-24-2008, 08:30 PM

I just wanted to thank everyone for posting their suggestions.

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

iMalc · 11-25-2008, 01:50 AM

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.

11-19-2008, 08:40 PM	#1
w2look Registered User 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. .
w2look is offline

11-19-2008, 08:41 PM	#2
master5001 Banned Join Date: Aug 2001 Location: Visalia, CA, USA Posts: 3,699	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.
master5001 is offline

11-19-2008, 09:11 PM	#3
blurx Registered User Join Date: Sep 2008 Posts: 45	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.
blurx is offline

11-19-2008, 11:28 PM	#5
P4R4N01D 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. __________________ 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); Last edited by P4R4N01D; 11-19-2008 at 11:31 PM. Reason: Added CODE tags
P4R4N01D is offline

11-19-2008, 11:45 PM	#6
Adak Registered User Join Date: Sep 2006 Posts: 2,510	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.
Adak is online now

11-24-2008, 08:30 PM	#7
w2look Registered User 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.
w2look is offline

11-25-2008, 01:50 AM	#8
iMalc Algorithm Dissector Join Date: Dec 2005 Location: New Zealand Posts: 2,476	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
iMalc is offline

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

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