Indexing with loops in python

107 views Asked by At

The question asks to write a function that takes in some unordered list and from that unordered list pull any sublist that is ordered. Example [5, 2, 1, 3, 4] would become [1,3,4]. My issue is in indexing, I want a way to express that if the current iteration is greater than the one before it, I want to add it. However, the problem that my code runs into is that it compares the first and last of an item.

For my code: [5, 2, 1, 3, 4] => [5,1,3,4]

def numIncreasing(lst):
    ans=[]
    for index in range(len(lst)):
        if lst[index]>=lst[index-1]:
            ans.append(lst[index])
        elif lst[index]<lst[index-1] and lst[index]<lst[index+1]:
            ans.append(lst[index])
        else:
            continue

    return ans

edit: fixed the code not recognizing the start of the pattern

1

There are 1 answers

8
RoadRunner On

Here is an algorithm that finds the largest ordered sublist:

def increasing2(lst):
    length = len(lst)

    for size in range(length, 1, -1):
        for start in range(0, length - size + 1):
            curr = lst[start:start+size]
            if all(x <= y for x, y in zip(curr, curr[1:])):
                return curr

    return None

Which behaves as follows:

>>> increasing2([5, 2, 1, 3, 4])
[1, 3, 4]

Logic of approach:

  • Loop over all sublists in reversed order, so the largest sublists come before the smaller sublists:

    [5, 2, 1, 3, 4]
    [5, 2, 1, 3]
    [2, 1, 3, 4]
    [5, 2, 1]
    [2, 1, 3]
    [1, 3, 4]
    [5, 2]
    [2, 1]
    [1, 3]
    [3, 4]
    
  • If the current list is sorted, return it. Otherwise keep going through all the sub lists in order from largest to smallest length. This ensures that you get the largest sublist first. The algorithm also only considers sublists of length 2 or greater.