I am trying to write a program that shows the longest ordered sequence in ascending order and its length.

For example:

input:

  lista = [43, 27, 28, 40, 43, 23, 29, 47, 37, 2, 14, 14, 18, 4, 27, 36, 24, 31,42, 29]

Output:

The maximum length = 4
The ordered values are = [27, 28, 40, 43]

I tried:

lista = [43, 27, 28, 40, 43, 23, 29, 47, 37, 2, 14, 14, 18, 4, 27, 36, 24, 31,42, 29]
#The ordered values are = [27, 28, 40, 43]
resultado = []
for i in range(0,len(lista)-1):
    for j in range(i 1,len(lista)):
        #print(lista[i],lista[j])
        if lista[i] < lista[j]:
            resultado.append(lista[i])
            resultado.append(lista[j])
        
            break
      
        break
print(resultado )  

The result:

[27, 28, 28, 40, 40, 43, 23, 29, 29, 47, 2, 14, 14, 18, 4, 27, 27, 36, 24, 31, 31, 42]

What is wrong?

CodePudding user response：

Form groups by a pairwise comparison. It returns the 1st match in case of multiple maximal sequences.

from itertools import groupby
from operator import itemgetter

lista = [43, 27, 28, 40, 43, 23, 29, 47, 37, 2, 14, 14, 18, 4, 27, 36, 24, 31,42, 29]

longest_asc_seq = max((list(next(grp))   list(map(itemgetter(1) , grp)) for check, grp in groupby(zip(lista, lista[1:]), key=lambda pair: pair[1] > pair[0]) if check), key=len)


print(f'The maximum length = {len(longest_asc_seq)}')
print(f'The ordered values are = {longest_asc_seq}')
#The maximum length = 4
#The ordered values are = [27, 28, 40, 43]

Remarks:

• with python 3.10 itertools.pairwise function is available instead of zip(lst, lst[1:])
• itemgetter can be replaced by a comprehension

CodePudding user response：

If you need a raw algorthim for this problem, this function will return the first sequence that has the longest ascendig order. It does not take into account when multiple sequences have the same length.

def longest_ascending_order(list_a):
    results = []
    right_number_index = 1
    left_number_index = 0
    # adds the start index
    cache_results = [list_a[left_number_index]]


    while right_number_index < (len(list_a)):


        #compares the two neigbour numbers. Exit condition for the ascending order
        if list_a[left_number_index] >= list_a[right_number_index]:
            # override the results if the new ascending order is longer
            if len(cache_results) > len(results):
                results = cache_results
            #reset the cache list
            cache_results = []

        # append number to the new sequence
        cache_results.append(list_a[right_number_index])

        right_number_index  = 1
        left_number_index  = 1

    print(results)
    return results


if __name__ == '__main__':
    list_of_numbers = [43, 27, 28, 40, 43, 23, 29, 47, 37, 2, 14, 14, 18, 4, 27, 36, 24, 31, 42, 29]
    longest_ascending_order(list_of_numbers)

CodePudding user response：

It does not answer your question, but i hope may be useful. I did it this way:

def f(x):
    res=[]
    temp=[]
    for i in x:
        if temp:
            if i>temp[-1]:
                temp.append(i)
            else:
                res.append(temp)
                temp=[i]
        else:
            temp.append(i)
    return max(res,key=len)