CodeBlanks Logo Icon CodeBlanks
Login Register

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.

Practice 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])).

Starter code

solution.py
def lis_length(arr):
    # Find LIS length with DP

Sample solution

solution.py
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]))

Expected output

4

Questions and answers

Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.

1 LIS condition

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

Explanation: > is right.

2 Challenge 2: match the terms

Term Meaning
LIS [2,3,7,101]
length 4
arr 8 elements
dp LIS array

3 What does LIS return?

  • All subsequences
  • Length of longest increasing subsequence Correct answer
  • Shortest subsequence
  • Sorted array

Explanation: LIS returns the length of the longest increasing subsequence.

All lessons in Advanced

1 DP - Memoization

  1. What is memoization?
  2. Fibonacci memoization
  3. Dict-based cache
  4. Summary - Memoization

2 DP - Tabulation

  1. What is tabulation?
  2. Building the table
  3. Fibonacci tabulation
  4. Summary - Tabulation

3 LCS

  1. LCS definition
  2. DP table
  3. Backtracking the table
  4. Summary - LCS

4 Knapsack

  1. Knapsack problem
  2. 0/1 knapsack DP
  3. Decision table
  4. Summary - Knapsack

5 DP project

  1. Project: Overview
  2. Cost table
  3. DP solution
  4. Print the result

6 Matrix chain

  1. Multiplication order
  2. DP table
  3. Split point
  4. Summary - Matrix chain

7 Floyd-Warshall

  1. All pairs
  2. Triple loop
  3. Table update
  4. Summary - Floyd-Warshall

8 Dijkstra

  1. Single source
  2. Priority queue
  3. Relaxation
  4. Summary - Dijkstra

9 Bellman-Ford

  1. Negative weights
  2. Edge relaxation loop
  3. Negative cycle
  4. Summary - Bellman-Ford

10 Kruskal

  1. Minimum spanning tree
  2. Edge sorting
  3. Cycle check
  4. Summary - Kruskal

11 Prim

  1. Prim idea
  2. Priority queue
  3. Visited set
  4. Summary - Prim

12 Topological sort

  1. Dependency order
  2. DFS-based sort
  3. Kahn algorithm
  4. Summary - Topological sort

13 Union-find, trie, segment tree

  1. Union-find
  2. Trie
  3. Segment tree
  4. Summary - Advanced structures

14 Advanced final

  1. Challenge 1
  2. Challenge 2
  3. Challenge 3
  4. Challenge 4