CODEWITHSUNDEEP
pythonlistalgorithmrecursionsequence
Saiko
Saiko

Reputation: 41

Python Recursion to Find The Longest Increasing Subsequence with Specific Limitations

I'm working on a problem where I need to implement a recursive function in Python to find the length of the longest increasing subsequence from a list of numbers. The list can have any length and can contain any integers. I'm only allowed to use the len() function and recursion to solve this problem, no loops, max(), helper functions or any other built-in functions are allowed.

Here's the problem description:

Given a list of numbers, find the length of the longest subsequence that creates a series of numbers that are strictly increasing. The order of the numbers in the list must not be changed to produce the increasing sequence, but numbers can be omitted.

For example, given the list [1, 5, 3, 4], the longest increasing subsequence is [1, 3, 4], therefore the resulting length is 3.

Here is my current attempt:

def longest_seq(lst, num=0):
    if not lst:
        return num
    if len(lst) == 1:
        return num + 1

    if lst[0] < lst[1]:
        return longest_seq(lst[1:], num + 1)
    if lst[0] >= lst[1]:
        if lst[0] < lst[2]:
            return longest_seq([lst[0]] + lst[2:], num)
        else:
            return longest_seq(lst[1:], num)

The function seems to work for some inputs, but I believe the logic is flawed. I've tried to address these issues, but I'm finding it challenging to come up with a solution that only uses recursion and len(), and doesn't modify the input list.

I understand that when lst[0] >= lst[1], my function should consider two possibilities:

But I'm struggling to implement this logic in my function. Can anyone suggest how I could improve my current implementation to handle these cases correctly?

Thank you in advance for your help.

** Apologies for any confusion caused. I removed the part where I mentioned it was against the rules. I would like to clarify that I am a beginner, so I may make mistakes from time to time. Regarding the question, I attempted to solve it by restricting myself to using only the len() function and employing recursive calls.

Upvotes: 0

Views: 638

Answers (3)

Alain T.
Alain T.

Reputation: 42133

The trick is to add an optional parameter to the function signature that will track the minimum value (previous included number in the sequence). The function then needs to compare the result of including versus excluding the first number when recursing with the rest of the list.

def longest_seq(L,previous=None):
    if not L: return 0
    included = excluded = longest_seq(L[1:],previous)
    if previous is None or L[0]>previous:
        included = 1 + longest_seq(L[1:],L[0])
    return included if included>excluded else excluded

output:

print(longest_seq([1,5,3,4]))         # 3
print(longest_seq([1,5,3,7,8,9]))     # 5
print(longest_seq([8,1,5,2,7,3,9,4])) # 4

Upvotes: 1

AlefiyaAbbas
AlefiyaAbbas

Reputation: 231

I have tried to answer the problem with a different approach. Basically, I have taken two variable include_first and exclude_first which represents the length of the longest increasing subsequence that includes the first element and excluding the first element respectively. I have tried some test cases which I will include below in the post. Let me know if the following helps:

def longest_seq(lst):
    if not lst:  
        return 0
    if len(lst) == 1:  
        return 1
    include_first = 1 + longest_seq(lst[1:]) if lst[0] < lst[1] else 0
    exclude_first = longest_seq(lst[1:])
    return max(include_first, exclude_first)

Test Cases:

print("Test Case 1:" ,longest_seq([1, 5, 3, 4]))
print("Test Case 2:", longest_seq([5, 2, 1, 0])) 
print("Test Case 3:", longest_seq([1, 2, 3, 4, 5]))  
print("Test Case 4:", longest_seq([5, 2, 8, 6, 3, 6, 9, 7]))

Output:

Test Case 1: 3
Test Case 2: 1
Test Case 3: 5
Test Case 4: 4

Upvotes: 1

wLui155
wLui155

Reputation: 742

Passing in a slice of the input list with the input removed is the correct idea. However, I'd suggest modifying your function so that it tracks the current largest element of the subsequence under consideration, as trying to achieve this by keeping lst[0] as the largest element (which is what I think is you're doing) won't work in general. I've gone ahead and provided a skeleton as to how this might look but left some of the recursive calls/details blank.

def longest_seq(lst, largest = None, num = 0):
    if not lst:
        return num

    rest = lst[1:] # the callee operates on the sublist of the lst, with lst[0] excluded
    if num == 0:
        include = longest_seq(rest, lst[0], 1) # In the callee, operate on rest, using lst[0] as the largest element. subsequence length is also 1 in the callee.
        exclude = None # TBD - how would the recursive call for i
        return None # TBD - larger between include/exclude

    # num > 0 => largest entry populated
    exclude = None # figure out the recursive call of not including lst[0]
    if lst[0] > largest: # can include current
        include = None # figure out recursive call
        return None # TBD - larger between include/exclude

    return exclude # could not include lst[0] in the subsequence so only exclude can be returned

Upvotes: 1

Related Questions