﻿ Python List - Length of the longest increasing sub-sequence

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

Python List Advanced: Exercise-2 with Solution

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:

What is the difficulty level of this exercise?

Test your Programming skills with w3resource's quiz.

﻿