Suppose we have two words made up from some letters, such as
We want to find the longest contiguous sequence of letters (subword) that is contained in both words. In this case, the longest common subword is "T G".
Solution
We calculate B[i,j] in an M x N array. We know the values in the last row and last column from the base case. Once we know the value at (i+1,j+1), we can compute the value at (i,j). So, we can systematically fill up the values for B[i,j] row by row, right to left, starting from the bottom (or, equivalently, column by column, bottom to top, starting from the right).
As before, we have two words over some letters, such as
Now we can drop some positions and obtain a subsequence. For instance "T G A C" is a subsequence of both words. Our aim is to find the length of the longest common subsequence.
Solution
Once again, we can fill up the values LCSS[i,j] in an M x N array, starting with the last row and column as base cases.
Fill the last row from right to left and once we fill a 1, all entries to the left are 1.
Similarly
Fill the last column from bottom to top and once we fill a 1, all entries above are 1.
The recurrences for LCSW and LCSS only tell us the lengths of the longest common subword and subsequence, respectively. How do we recover a witness — that is, a common subword or subsequence of this maximum length?
For subword it is easy — since we know the position where the longest common subword starts, we can read off the subword.
How do we do it for longest common subsequence?
Let s = a[1] a[2] ... a[n] be an unsorted sequence of numbers. A subsequence of s is one in which we drop some elements and retain the rest (so we need not pick up a contiguous segment, but we preserve the order of elements).
For instance, a[1] a[3] a[n] is a subsequence.
Problem: Find the (length of the) longest ascending subsequence.
Solution 1
Sort the array and find the longest common subsequence between sorted sequence and original sequence.
This takes time O(n^{2}) (sorting takes time O(n log n) and longest common subsequence takes O(n^{2}).
Solution 2
A direct dynamic programming solution for this problem.
This can be computed in an array. This takes time O(n^{2}) — for each LAS[i], we have to scan values from LAS[1] to LAS[i-1].
This solution is no better than our initial solution of sorting the sequence and then computing the longest common subsequence.
We can improve the second solution to solve the problem in O(n log n) by maintaining an additional array M.
Observe that M[j]'s always form an ascending sequence. So, we can find M[j-1] <= a[i] < M[j] using binary search.
Adding a[i] requires log(i) time. Overall we make n updates, so the overall algorithm is O(n log n).
An example:
i 1 2 3 4 5 6 7 8 a[i] 8 2 7 3 9 4 6 5 LAS[i] 1 1 2 2 3 3 4 4 M[i] 8X 7X 9X 6X 2 3 4 5
Given a sequence of integers, a subsection is a block of contiguous integers in the sequence. The task is to find the subsection whose sum is maximum.
For instance, here is a sequence and a subsection marked out whose sum is -1.
3 -1 2 -1 2 -3 4 -2 1 2 1 |<------------>| sum = -1
Find an O(N) algorithm for this problem.
Solution
This assumes subsections are of length > 0. If zero length segments are permitted, we also have to add a term 0 to the max term when computing Best(i). (For instance, if all values are negative, the maximum sum subsection would then be the empty subsection with sum 0.)
Video lecture on Dynamic programming, classic problems, NPTEL online course on Design and Analysis of Algorithms
©IARCS 2012–2016
PÄ›stujeme web | visit: Skluzavky