0 Replies - 1367 Views - Last Post: 09 October 2011 - 11:31 AM

#1 Simown   User is offline

  • Blue Sprat
  • member icon

Reputation: 322
  • View blog
  • Posts: 650
  • Joined: 20-May 10

Longest Increasing Subsequence - Python

Posted 09 October 2011 - 11:31 AM

Description: Use as a function, taking a sequence as a parameter >>> LIS([2, 3, 4, 2, 7, 8, 9, 10, 11, 4, 6, 7]) [7, 8, 9, 10, 11] >>> LIS([[1, 3, 2, 4, 5, 11, 9, 6, 5, 6, 7]) [4, 5, 11]Returns the longest subsequence in the input sequence. It does NOT return the longest subset. It will return the first longest subsequence in the input sequence.
def LIS(seq):
	maxSeq = []
	s = [seq[0]]
	for i in range (1, len(seq)):
		if seq[i-1] < seq[i]:
			s.append(seq[i])
		else:
			if len(s) > len(maxSeq): 
				maxSeq = s
			s = []
	return maxSeq


Is This A Good Question/Topic? 0
  • +

Page 1 of 1