CODEWITHSUNDEEP
pythonalgorithm
Greg Leclercq
Greg Leclercq

Reputation: 138

Counter example that show that this longest increasing subsequence algorithm is wrong

could someone tell me what's wrong with the following algorithm to find the longest increasing subsequence in a sequence of integers:

def longest_increasing_subsequence(sequence):
  """

  Examples:

  >>> longest_increasing_subsequence([])
  []
  >>> longest_increasing_subsequence([1])
  [1]
  >>> longest_increasing_subsequence([1, 2])
  [1, 2]
  >>> longest_increasing_subsequence([2, 1])
  [1]
  >>> longest_increasing_subsequence([1, 2, 3])
  [1, 2, 3]
  >>> longest_increasing_subsequence([3, 1, 2])
  [1, 2]
  >>> longest_increasing_subsequence([5, 1, 3, 2, 6])
  [1, 2, 6]
  >>> longest_increasing_subsequence([1, 6, 3, 5, 9, 7])
  [1, 3, 5, 7]
  >>> longest_increasing_subsequence([3, 1, 2, 4, 6])
  [1, 2, 4, 6]
  >>> longest_increasing_subsequence([0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15])
  [0, 4, 6, 9, 11, 15]
  >>> longest_increasing_subsequence([1, 10, 2, 9, 3, 8, 4, 7, 5, 6])
  [1, 2, 3, 4, 5, 6]

  """
  if not sequence:
      return []

  result = [sequence[0]]
  for i in sequence[1:]:
      if i < result[0]:
          result = [i]
      elif i > result[-1]:
          result.append(i)
      elif len(result) >= 2 and i > result[-2]:
              result[-1] = i

  return result

Do you find a counter-example that makes it return a wrong result?

Upvotes: 0

Views: 128

Answers (1)

cchristelis
cchristelis

Reputation: 2015

The problem with your logic is that you assume the longest increasing subsequence begins with the lowest number. This is a fallacy as shown in:

>>> longest_increasing_subsequence([2, 3, 4, 5, 6, 1])
[1]

Upvotes: 3

Related Questions