Python List Advanced Exercise - Length of the longest increasing sub-sequence

Last update on December 21 2024 07:34:00 (UTC/GMT +8 hours)

Write a Python function find the length of the longest increasing sub-sequence in a list.

Sample Solution:

Python Code:

 # Define a function to find the length of the longest increasing subsequence in a list
def longest_increasing_subsequence(nums):
    # Get the length of the input list
    n = len(nums)
    
    # Create a list 'arr' to store the length of the longest increasing subsequence
    arr = [1] * n
    
    # Iterate over the elements in the list
    for i in range(1, n):
        # Iterate over elements before the current element 'i'
        for j in range(i):
            # Check if the current element is greater than the previous element
            if nums[i] > nums[j]:
                # Update the length of the longest increasing subsequence for the current element 'i'
                arr[i] = max(arr[i], arr[j] + 1)
    
    # Return the maximum value in the 'arr' list, which represents the length of the longest increasing subsequence
    return max(arr)

# Create a list of numbers
nums = [10, 20, 30, 40, 50, 60, 70, 80]

# Print the original list
print("Original list:")
print(nums)

# Call the longest_increasing_subsequence function and print the result
print("Length of the longest increasing sub-sequence in the said list:")
print(longest_increasing_subsequence(nums))

# Create another list of numbers
nums = [10, 20, 30, 40, 50, 30, 30, 20]

# Print the original list
print("\nOriginal list:")
print(nums)

# Call the longest_increasing_subsequence function with the second list and print the result
print("Length of the longest increasing sub-sequence in the said list:")
print(longest_increasing_subsequence(nums))

# Create a third list of negative numbers
nums = [-1, -2, -3, -4, -5, -11, -12, -13]

# Print the original list
print("\nOriginal list:")
print(nums)

# Call the longest_increasing_subsequence function with the third list and print the result
print("Length of the longest increasing sub-sequence in the said list:")
print(longest_increasing_subsequence(nums))

Sample Output:

Original list:
[10, 20, 30, 40, 50, 60, 70, 80]
Length of the longest increasing sub-sequence in the said list:
8

Original list:
[10, 20, 30, 40, 50, 30, 30, 20]
Length of the longest increasing sub-sequence in the said list:
5

Original list:
[-1, -2, -3, -4, -5, -11, -12, -13]
Length of the longest increasing sub-sequence in the said list:
1

Flowchart:

What is the time complexity and space complexity of the following Python code?

def longest_increasing_subsequence(nums):
    n = len(nums)
    arr = [1] * n
    for i in range(1, n):
        for j in range(i):
            if nums[i] > nums[j]:
                arr[i] = max(arr[i], arr[j]+1)
    return max(arr)

Time complexity - The time complexity of the given code is O(n^2), where n is the length of the input array “nums”. This is because there are two nested loops, each ranging from 0 to n-1. Therefore, the total number of iterations is n*(n-1)/2, which is O(n^2) in the worst case.

Space complexity - This code has a space complexity of O(n), since it uses an additional array "arr" to store the lengths of the increasing subsequences ending at each index of "nums".

Python Code Editor:

Previous: Reverse a list at a specific location.
Next: Permutations of the members of a list.