Skip to content

Instantly share code, notes, and snippets.

@tahia-khan tahia-khan/ZigZag.py
Created May 25, 2016

Embed
What would you like to do?
class State:
def __init__(self, longest_sequence, next_diff):
""" next_diff = 1 means the next expected difference
in the zigzag sequence is positive
next_diff = 0 means the next expected difference
in the zigzag sequence is negative """
self.longest = longest_sequence
self.next_diff = next_diff
def __repr__(self):
return "(%d, %d)" % (self.longest, self.next_diff)
class ZigZag:
def longestZigZag(self, sequence):
L = len(sequence)
M = [State(0,0)] * L
# Corner case: first 'start' numbers of the sequence are the same
start = 1
while sequence[start] == sequence[start-1]:
start += 1
# Set initial state of first unique number in sequence
if sequence[start] > sequence[start-1]:
M[start] = State(1, 0)
else:
M[start] = State(1, 1)
start += 1
for i in range(start, L):
longest = 0
next_diff = 0
for j in range(i-1, -1, -1):
prev_state = M[j]
if longest > prev_state.longest:
break
diff = sequence[i] - sequence[j] # current - prev
if prev_state.next_diff and diff > 0:
longest = max(longest, prev_state.longest + 1)
next_diff = 0
elif not prev_state.next_diff and diff < 0:
longest = max(longest, prev_state.longest + 1)
next_diff = 1
else:
longest = prev_state.longest
next_diff = prev_state.next_diff
M[i] = State(longest, next_diff)
return M[L-1].longest + 1
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.