• Post Reply Bookmark Topic Watch Topic
  • New Topic

Finding the longest Zig-Zag sequence in an array.  RSS feed

 
Kaspersky Ukshini
Ranch Hand
Posts: 122
C++ Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I don't know if this title makes sense at all, but I'll try to explain lol...
From a given array of positive and negative numbers, I have to find the longest SUB-Array which represents a Zig-Zag sequence...
A Zig-Zag sequence means that one number is possitive, the next one negative, the next one possitive, and so on and so on...
Like this: -1, 4, -5, 6, -9, 2, -9 etc....

So that means, if the array looks like this:

1, 4, -2, -5, 6, -9, 1, -4, 9, -8, 7, 4, -3

the longest sub-array which fulfills the requirement is (the part in bold):
1, 4, -2, -5, 6, -9, 1, -4, 9, -8, 7, 4, -3

and I only need it's length, which in this case is: 8
-----------
Can someone give me an idea on how to solve this?
I have now gotten pretty comfortable with the syntax of the language Java, I only need ideas so far...

Thank you!
 
K. Tsang
Bartender
Posts: 3648
16
Firefox Browser Java Mac OS X
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Welcome to the Ranch.

The way I see it is like this:
have a int variable to keep zig-zag count
have a boolean variable to check "previous" number is positive
have a boolean variable to check "previous" number is negative
stuff the numbers in an array or list
loop through the array or list, checking each number is positive or negative
check current number has same sign as previous number, if so reset the zig-zag count to 0, if not increment the zig-zag count



Exactly how to keep track of the "previous" number's sign (using one variable, 2 variables) is something you need to think about.
 
Kaspersky Ukshini
Ranch Hand
Posts: 122
C++ Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
What do you suggest would be better... DoublyLinkedList or just an Int array?
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Kaspersky Ukshini wrote:What do you suggest would be better... DoublyLinkedList or just an Int array?

An array. This problem (I'm pretty sure) is meant to test your understanding of how to get the longest subsequence according to the rules supplied; not your knowledge of the Java Collections API.

You may find this page useful, but it's geared more to finding matching values in Strings. In your case, the "match" only involves two possibilities: positive or negative (although you might want to think about how you handle 0), but the approach is basically the same.

HIH

Winston

[Edit:] Actually, thinking about it, that page may be the next stage for this sort of problem (so possibly still worth a read, but don't worry about it too much ). K.Tsang's solution is much better.

Think about it: If you were asking a 10-year old child to do this with a line of numbered blocks, what would you tell THEM to do?
 
Kaspersky Ukshini
Ranch Hand
Posts: 122
C++ Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I think I have an idea on how to try and solve it.. one thing...what to do with the 0? count it as a "party breaker" or what shoud I call it lol... for example if I find a zero, it stops my sequence? or check it's sing in front... it sounds stupid, but can I have a number -0 and 0 ?
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Kaspersky Ukshini wrote:I think I have an idea on how to try and solve it.. one thing...what to do with the 0? count it as a "party breaker" or what shoud I call it lol... for example if I find a zero, it stops my sequence? or check it's sing in front... it sounds stupid, but can I have a number -0 and 0 ?

Answers:
1. Entirely up to you. Just make sure you DOCUMENT your decision.
2. (±0) Yes, but not in an int; double, on the other hand, supports both; and Double actually distinguishes the two.

My advice: forget ±0, and concentrate on the problem.

Winston
 
Kaspersky Ukshini
Ranch Hand
Posts: 122
C++ Java
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Until now, this is what I've come up with..but it doesn't really seem to be correct lol.
P.S: every array that has only ONE element, which is NOT zero, is considered as sequence of 1.... one part of the code is wrriten to check this..





EDIT : I finished it! THANK YOU SO MUCH GUYS!!!
 
Bowerick Wowbagger
Greenhorn
Posts: 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Kaspersky Ukshini wrote:Until now, this is what I've come up with..but it doesn't really seem to be correct lol.
P.S: every array that has only ONE element, which is NOT zero, is considered as sequence of 1.... one part of the code is wrriten to check this..





EDIT : I finished it! THANK YOU SO MUCH GUYS!!!



Is this the correct code? If not, can you send me the one that works please? Thanks.
 
K. Tsang
Bartender
Posts: 3648
16
Firefox Browser Java Mac OS X
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Bowerick Wowbagger wrote:Is this the correct code? If not, can you send me the one that works please? Thanks.


Welcome to the Ranch

Are you in the same class as Kaspersky or something?

If you feel or tested the code is incorrect, why don't you correct it? Are there any areas that can be improved?
 
Joe Harry
Ranch Hand
Posts: 10128
3
Eclipse IDE Mac PPC Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I could not resist myself from posting a recursive solution. It uses the so called accumulator pattern that I got to learn during a Scala course that I took. Here is the Scala version of it. It can easily be adapted to Java as well!

 
Joanne Neal
Rancher
Posts: 3742
16
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
K. Tsang wrote:Are you in the same class as Kaspersky or something?

And if you are, don't forget that plagiarism will probably get you a zero score.
 
Kaspersky Ukshini
Ranch Hand
Posts: 122
C++ Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Joe Harry wrote:I could not resist myself from posting a recursive solution. It uses the so called accumulator pattern that I got to learn during a Scala course that I took. Here is the Scala version of it. It can easily be adapted to Java as well!



Another way of solving it won't hurt lol..thanks a lot buddy!

Joanne Neal wrote:
K. Tsang wrote:Are you in the same class as Kaspersky or something?

And if you are, don't forget that plagiarism will probably get you a zero score.


That is exactly what I was gonna write... I can offer help too, now that I know the solution, but I can't post the same code, cause we can be punished badly for plagiarisms, like not being allowed to take the exam.
 
Joe Harry
Ranch Hand
Posts: 10128
3
Eclipse IDE Mac PPC Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The point I wanted to convey through my solution is that the less code you write, the less chances of error!
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!