How to find longest consistent increment in a python list?

Question

possible_list = []
bigger_list = []

new_list= [0, 25, 2, 1, 14, 1, 14, 1, 4, 6, 6, 7, 0, 10, 11]
for i in range(0,len(new_list)):
   # if the next index is not greater than the length of the list
    if (i + 1) < (len(new_list)):
         #if the current value is less than the next value
         if new_list[i] <= new_list[i+1]:
             # add the current value to this sublist
             possible_list.append(new_list[i])
             # if the current value is greater than the next, close the list and append it to the lager list
         bigger_list.append(possible_list)
print bigger_list

How do I find the longest consistent increment in the list called new_list? I expect the result to be

[[0,2], [2], [1,14], [1,14], [1,4,6,6,7], [0,10,11]]

I can find the remaining solution from there myself.

possible duplicate of [Longest increasing subsequence](http://stackoverflow.com/questions/3992697/longest-increasing-subsequence) — Ami Tavory, Jun 16 '15 at 07:47
@tobias_k Thanks for the correction. it was a typographical error. — ebenezer popoola, Jun 16 '15 at 08:20
@AmiTavory the solution tobias_k gave is simple and straightforward. Kudos to him. — ebenezer popoola, Jun 16 '15 at 08:31
@ebenezerpopoola What does the quality of an answer have to do with the issue of whether your question is a duplicate? — Ami Tavory, Jun 16 '15 at 08:45
@AmiTavory This is not the same problem. Longest increasing subsequence can be non-continuous, this one is about continuous non-increasing segments of the list. — tobias_k, Jun 16 '15 at 08:50
@tobias_k OK, that is relevant - I missed that. Thanks for the correction. — Ami Tavory, Jun 16 '15 at 08:51

score 3 · Accepted Answer · answered Jun 16 '15 at 07:59

One problem (but not the only one) with your code is that you are always adding the elements to the same possible_list, thus the lists in bigger_list are in fact all the same list!

Instead, I suggest using [-1] to access the last element of the list of subsequences (i.e. the one to append to) and [-1][-1] to access the last element of that subsequence (for comparing the current element to).

new_list= [0, 25, 2, 1, 14, 1, 14, 1, 4, 6, 6, 7, 0, 10, 11]    
subseq = [[]]
for e in new_list:
    if not subseq[-1] or subseq[-1][-1] <= e:
        subseq[-1].append(e)
    else:
        subseq.append([e])

This way, subseq ends up the way you want it, and you can use max to get the longest one.

>>> subseq
[[0, 25], [2], [1, 14], [1, 14], [1, 4, 6, 6, 7], [0, 10, 11]]
>>> max(subseq, key=len)
[1, 4, 6, 6, 7]

tobias_k thanks for the answer. you really understood the question well. you just made my day — ebenezer popoola, Jun 16 '15 at 08:10

How to find longest consistent increment in a python list?

1 Answers1

Linked

Related