# 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:**

**Previous:** Reverse a list at a specific location.

**Next:** Permutations of the members of a list.

**What is the difficulty level of this exercise?**

Test your Programming skills with w3resource's quiz.

**Weekly Trends and Language Statistics**- Weekly Trends and Language Statistics