Extracting the subsequence of maximum length from a sequence [PYTHON]

Question

I have a sequence of values [1,2,3,4,1,5,1,6,7], and I have to find the longest subsequence of increasing length. However, the function needs to stop counting once it reaches a number lower than the previous one. The answer in this sequence in that case is [1,2,3,4]. As it has 4 values before being reset. How would I write the Python code for this?

Note: Finding the "longest increasing subsequence" seems to be a common challenge and so searching online I find a lot of solutions that would count for the entire length of the sequence, and return a subsequence of increasing values, ignoring any decrease, so in this case it would return [1,2,3,4,5,6,7]. That is not what I'm looking for.

It needs to count each subsequence, and reset the count upon reaching a number lower than the previous one. It then needs to compare all the subsequences counted, and return the longest one.

Thanks in advance.

Answer 1

Consider a function that generates all possible ascending subsequences, you would start with an empty list, add items until one element was less (or equal to?) the the previous at which point you save (yield) the subsequence and restart with a new subsequence.

One implementation using a generator could be this:

def all_ascending_subsequences(sequence):
    #use an iterator so we can pull out the first element without slicing
    seq = iter(sequence)

    try: #NOTE 1
        last = next(seq)  # grab the first element from the sequence
    except StopIteration: # or if there are none just return
        #yield [] #NOTE 2
        return

    sub = [last]
    for value in seq:
        if value > last: #or check if their difference is exactly 1 etc.
            sub.append(value)
        else: #end of the subsequence, yield it and reset sub
            yield sub
            sub = [value]
        last = value

    #after the loop we send the final subsequence
    yield sub

two notes about the handling of empty sequences:

1. To finish a generator a StopIteration needs to be raised so we could just let the one from next(seq) propegate out - however when from __future__ import generator_stop is in effect it would cause a RuntimeError so to be future compatible we need to catch it and explicitly return.
2. As I've written it passing an empty list to all_ascending_subsequences would generate no values, which may not be the desired behaviour. Feel free to uncomment the yield [] to generate an empty list when passed an empty list.

Then you can just get the longest by calling max on the result with key=len

b =  [1,2,3,4,1,5,1,6,7]

result = max(all_ascending_subsequences(b),key=len)
print("longest is", result)

#print(*all_ascending_subsequences(b))

Answer 2

b = [4,1,6,3,4,5,6,7,3,9,1,0]

def findsub(a):
  start = -1
  count = 0
  cur = a[0]
  for i, n in enumerate(a):
    if n is cur+1:
      if start is -1:
        start = i - 2
        count=1
      count+=1
      cur = n
    if n < cur and count > 1:
      return [a[j] for j in range(start,start+count+1)]


print findsub(b)

A somewhat sloppy algorithm, but I believe it does what you want. Usually i would not have simply shown you code, but I suspect that is what you wanted, and I hope you can learn from it, and create your own from what you learn.

a slightly better looking way because I didn't like that:

b = [1,2,0,1,2,3,4,5]

def findsub(a):
  answer = [a[0]]
  for i in a[1:]:
    if answer[-1] + 1 is i:
      answer.append(i)
    if not len(answer) > 1:
      answer = [i]
    elif i < answer[-1] and len(answer) > 1:
      return answer
  return answer



print findsub(b)

Answer 3

You need to do the following:

1. Create a function W that given a list, returns the index of the last item which is not strictly increasing from the start of the list.

   • For example, given the following lists: [1,2,3,4,1,2,3], [4,2,1], [5,6,7,8], it should return 4, 1, 4, respectively for each list

2. Create a variable maxim and set the value to 0

3. Repeatedly do the following until your list is empty
   • Call your function W on your list, and let's call the return value x
   • if x is greater than maxim
     • set maxim to x
     • At this point if you wish to store this sequence, you can use the list-slice notation to get that portion of your list which contains the sequence.
   • delete that portion of your list from the list

Finally, print maxim and if you were storing the parts of your list containing the longest sequence, then print the last one you got