How can I optimize the below code that I have written for this problem? Can I get some suggestions?
Given an array of integer elements, find the length of the longest subsequence such that all elements are alternating. If a sequence {x1, x2, .. xn} is alternating sequence then its element satisfies one of the following relations:
x1 < x2 > x3 < x4 > x5 < …. xn
or
x1 > x2 < x3 > x4 < x5 > …. xn
Input:
8
10 22 9 33 49 50 31 60
where: First line represents the number of elements in the array. Second line represents the array elements.
Output:
6
Explanation:
The subsequence {10, 22, 9, 33, 31, 60} is in the format x1 < x2 > x3 < x4 > x5 < x6 i.e. { 10 < 22 > 9 < 33 > 31 < 60 } and it is the largest of this form and the length of this subsequence is 6, hence the output 6.
n = int(input())
L = []
for e in input().split():
L.append(int(e))
count, i = 0, 0
flag = None
while i < (len(L) - 1):
for j in range(i+1, len(L)):
if count == 0 and flag is None:
if (L[i] < L[j]):
count+=1
flag = 1
i = j
break
elif (L[i] > L[j]):
count+=1
flag = 0
i = j
break
else:
i = j
else:
if (flag == 0) and (L[i] < L[j]):
count+=1
flag = 1
i = j
break
elif (flag == 1) and (L[i] > L[j]):
count+=1
flag = 0
i = j
break
else:
i = j
print(count+1)
You can iterate the list while keeping a reference to the previous node that did not contribute to the alternating pattern.
We start at setting the prev_node as the first element in the list. The loop starts at index 1 and iterates till the end. For each value, it compares the value with prev_node. If it is of an alternating pattern, increment the max_lenght, and update prev_node.
LT = -1 # Less than
GT = 1 # Greater than
max_length = 1
prev_node = L[0] # Begin at 0
prev_compare = 0
found = 0
for i in range(1, len(L)):
if L[i] < prev_node:
if prev_compare != LT:
prev_compare = LT
found = True
elif L[i] > prev_node:
if prev_compare != GT:
prev_compare = GT
found = True
# If an alternating node is found
if found:
max_length += 1
prev_node = L[i]
found = False
print(max_length)
From your comments, I assume you don't really care much about readability of code.
I have a short version (in terms of character count) of the same algorithm as above. The logic is basically the same, thus the performance is the same.
nodes = [L[0]]
prev_compare = -1
for e in L[1:]:
if e != nodes[-1] and (e > nodes[-1]) != prev_compare:
prev_compare = e > nodes[-1]
nodes += [e]
print(len(nodes))