Find the longest increasing subarray-CodePudding

For example : input = [1,2,3,1,5,7,8,9] , output = [1,5,7,8,9]

find out the longest continuous increasing subarray

I have tried on my own like this :

def longsub(l):
    newl = []
    for i in range(len(l)) :
        if l[i] < l[i 1] :
            newl.append(l[i])
        else :
            newl = []
    return newl

But it would get error since the list index out of range. (It could not get the value after last value)

def longsub(l):
    newl = []
    for i in range(len(l)) :
        if l[i] > l[i-1] :
            newl.append(l[i])
        else :
            newl = []
    return newl

And then I did this, but I would get the result without the first value of increasing subarray.

What should I rectify my code? Thanks!

CodePudding user response：

Suppose that you had this helper at your disposal:

def increasing_length_at(l, i):
    """Returns number of increasing values found at index i.

    >>> increasing_length_at([7, 6], 0)
    1
    >>> increasing_length_at([3, 7, 6], 0)
    2
    """
    val = l[i] - 1
    for j in range(i, len(l)):
        if l[j] <= val:  # if non-increasing
            break
        val = l[j]
    return j - i

How could you use that as part of a solution?

CodePudding user response：

Firstly, you can use len(l) - 1 to avoid the IndexError. However, your approach is invalid since this would just return the last increasing sub. Here's my approach:

def longsub(l):
    res, newl = [], []
    for i in range(len(l)-1):
        if l[i] < l[i 1]:
            newl.append(l[i])
        else:
            newl.append(l[i])
            res.append(newl)
            newl = []
    if newl: res.append(newl)
    return max(res, key=len)
input = [1,2,3,4,5,1,5,7,8,9]
print(longsub(input))

Output:

>>> [1, 2, 3, 4, 5]

CodePudding user response：

Another solution: skip indexing and leverage Python generators combine them with built-in max() function with custom key=:

def grouper(lst):
    if not lst:
        return lst

    out = [next(i := iter(lst))]
    for val in i:
        if val > out[-1]:
            out.append(val)
        else:
            yield out
            out = [val]

    yield out


lst = [1, 2, 3, 1, 5, 7, 8, 9]
print(max(grouper(lst), key=len))

Prints:

[1, 5, 7, 8, 9]