Sequences & Strings (LIS, LCS, Edit Distance)

1function LIS(arr):
2  n = len(arr)
3  dp = array(n, 1)
4  best = 1
5  for i in 0..n-1:
6    for j in 0..i-1:
7      if arr[j] < arr[i]:
8        dp[i] = max(dp[i], dp[j] + 1)
9    best = max(best, dp[i])
10  return best

1function LCS(a, b):
2  n = len(a); m = len(b)
3  dp = array(n+1, m+1, 0)
4  for i in 1..n:
5    for j in 1..m:
6      if a[i-1] == b[j-1]:
7        dp[i][j] = 1 + dp[i-1][j-1]
8      else:
9        dp[i][j] = max(dp[i-1][j], dp[i][j-1])
10  return dp[n][m]

1function editDistance(a, b):
2  n = len(a); m = len(b)
3  dp = array(n+1, m+1, 0)
4  for i in 0..n: dp[i][0] = i
5  for j in 0..m: dp[0][j] = j
6  for i in 1..n:
7    for j in 1..m:
8      if a[i-1] == b[j-1]:
9        dp[i][j] = dp[i-1][j-1]
10      else:
11        dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
12  return dp[n][m]