Challenge 2

Compute and print the LCS length.

Challenge 2: LIS

In this challenge you will solve the longest increasing subsequence (LIS) problem. You will find the longest increasing subsequence in an array.

Array is [10, 9, 2, 5, 3, 7, 101, 18]. The LIS length is 4. Produce this with DP.

Exercise lis_length function

Write lis_length(arr). With DP, find the longest increasing subsequence length for each i. Print 4 with print(lis_length([10, 9, 2, 5, 3, 7, 101, 18])).

Show example solution

def lis_length(arr):
    # Find LIS length with DP
    dp = [1] * len(arr)
    for i in range(1, len(arr)):
        for j in range(i):
            if arr[i] > arr[j]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)
print(lis_length([10, 9, 2, 5, 3, 7, 101, 18]))

Test yourself

LIS condition

if arr[i] ____ arr[j]: dp[i] = max(dp[i], dp[j] + 1)

Show answer

if arr[i] > arr[j]: dp[i] = max(dp[i], dp[j] + 1)

Challenge 2: match the terms

LIS

[2,3,7,101]
length

4
arr

8 elements
dp

LIS array
What does LIS return?
- All subsequences
- Length of longest increasing subsequence
- Shortest subsequence
- Sorted array
Show answer

Length of longest increasing subsequence — LIS returns the length of the longest increasing subsequence.

Next lesson: Challenge 3

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies