7 3 4 9 2 8 4 5 2 1 6 3 10then the length of the longest decreasing subsequence in this sequence is: 5, and in this case there are two such maximal subsequences:
9 8 5 2 1 9 8 4 2 1The input-output description of this problem is:
Input: A sequence S = a1,a2,...,an (you can assume that the sequence is stored in an array) of length n, where each ai is a real number.
Output: Your pseudo-code should print the following output:
Solve this problem following the steps below.
Solution
Given a sequence a1...an, we divide the problem into the following n overlapping subproblems:SubPbm 1: Find the longest strictly decreasing subsequence in a1 that ends in a1 SubPbm 2: Find the longest strictly decreasing subsequence in a1 a2 that ends in a2 SubPbm 3: Find the longest strictly decreasing subsequence in a1 a2 a3 that ends in a3 ... SubPbm j: Find the longest strictly decreasing subsequence in a1 a2 a3 ... aj that ends in aj ... SubPbm n: Find the longest strictly decreasing subsequence in a1 a2 a3 ... aj... an that ends in anWe will use an array OPT[0..n] to store the solution to each of these subproblems:P[j] = Length of the longest strictly decreasing subsequence in a1...aj that ends in aj.
- Boundary condition: P[0]=0
- Recurrence: We will solve problem j using the solutions to problems 0,...,j-1 as follows: The longest subsequence in in a1 a2 a3 ... aj that ends in aj would result from concatenating the longest subsequence in a1 a2 a3 ... a(j-1) that ends in an element that is strictly greater than aj. In other words:
OPT[j] = 1 + (max over all i < j with ai > aj {OPT[i]}) As an illustration, note that for the given example,
Sequence: 7 3 4 9 2 8 4 5 2 1 6 3 10 Index: 1 2 3 4 5 6 7 8 9 10 11 12 13 we have: OPT[0]=0 OPT[1]=1 the longest strictly decreasing subsequence in 7 ending in 7 has length 1 (namely 7) OPT[2]=2 the longest strictly decreasing subsequence in 7 3 ending in 3 has length 2 (namely 7 3) OPT[3]=2 the longest strictly decreasing subsequence in 7 3 4 ending in 4 has length 2 (namely 7 4) OPT[4]=1 the longest strictly decreasing subsequence in 7 3 4 9 ending in 9 has length 1 (namely 9) OPT[5]=3 the longest strictly decreasing subsequence in 7 3 4 9 2 ending in 2 has length 3 (namely 7 3 2 or 7 4 2) OPT[6]=2 the longest strictly decreasing subsequence in 7 3 4 9 2 8 ending in 8 has length 2 (namely 9 8) OPT[7]=3 the longest strictly decreasing subsequence in 7 3 4 9 2 8 4 ending in 4 has length 3 (namely 9 8 4) and so on. Note for instance that OPT[7] = 1 + (max over all i < 7 with ai > 4 {OPT[i]}) = 1 + (max {OPT[1],OPT[4],OPT[6]}) = 1 + (max {1,1,2}) = 1 + 2 = 3- Proof of Correctness of this Recurrence: Let's prove that this recurrence is correct. As expected, we'll prove it by induction.
- Base Case: For j=0: OPT[0]=0 correctly as the lenght of the longest strictly decreasing subsequence of an empty is 0.
- Induction Step: Let 0 ≤ j ≤ n.
Induction Hypothesis: Assume that for each i < j we have that P[i] correctly contains the length of the longest strictly decreasing subsequence in a1...ai that ends in ai.Now let's prove that this property holds for j too.OPT[j] = 1 + (max over all i < j with ai > aj {OPT[i]}) by definition of OPT[j] = 1 + (max over all i < j with ai > aj {length of the longest strictly decreasing subsequence in a1...ai that ends in ai} by the induction hypothesis = length of the longest subsequence in a1...aj-1 that ends in a number greater than aj and since we can concatenate aj to this subsequence keeping it strictly decreasing, then we add 1 to obtain the length of the resulting subsequence = length of the longest strictly decreasing subsequence in a1...aj that ends in aj Hence, the property holds for j too.- Solution to Full Problem: Once that all the P[j]'s are computed for 1 ≤ j ≤ n, the solution to the full problem (the lenght of the longest strictly decreasing subsequence in S) is equal to the maximum value in this array:
max over all i, 1 ≤ i ≤ n {OPT[i]}
In the example above, the maximum value in OPT[0...n] will be OPT[10]=5 as 9 8 5 2 1 (or equivalently, 9 8 5 2 1) is the longest strictly decreasing subsequence.
- Longest Subsequence: We can optionally use an additional array to keep track of the longest subsequence (not just of its length): PREV[0...n] where:
PREV[j] = Index of the element in a1...a(j-1) that comes right before aj in the longest strictly decreasing subsequence in a1...aj that ends in aj.
For instance, PREV[7]=6 in the example above. PREV[5]=2 if the subsequence 7 3 2 is chosen over 7 4 2 or PREV[5]=3 if vice versa.
We could find the optimal subsequence without keeping the PREV array as it will be shown in the algorithm below.
Solution
Find-longest-strictly-decreasing-subsequence(a1...an) { Array OPT[0...n] of integers Array PREV[0...n] of integers OPT[0]:=0 O(1) PREV[0]:=0 O(1) For j := 1 to n do { n*O(1) // here it would be enough to say: OPT[j] = 1 + (max over all i < j with ai > aj {OPT[i]}) but below we provide a detailed implementation of this recurrence // max-so-far := 0 n*O(1) best-prev-so-far := 0 n*O(1) For i := 1 to j-1 do { n2*O(1) If ai > aj Then { n2*O(1) If OPT[i] > max-so-far Then { n2*O(1) max-so-far := OPT[i] n2*O(1) best-prev-so-far := i n2*O(1) } } } OPT[j]:= 1 + max-so-far n*O(1) PREV[j] := best-prev-so-far n*O(1) //Alternatively, we could define a graph in which each j is a node and there is an edge from j to i IFF i < j AND ai > aj. Hence, OPT[j] = 1 + (max over all i < j with ai > aj {OPT[i]}) can be easily calculated as: OPT[j] = 1 + (max over all i such that (j,i) exists {OPT[i]}) } Let k be the index of the maximum value in the array OPT[1...n] (or such one index if the maximum value appears more than once in the array) O(n) Print that the length of the longest strictly decreasing subsequence in a1...an is OPT[k] O(1) Call Print-longest-strictly-decreasing-subsequence1 with array PREV[0...n] and k O(n) or alternatively Call Print-longest-strictly-decreasing-subsequence2 with array OPT[0...n] and k O(n) } Print-longest-strictly-decreasing-subsequence1(array PREV[0...n], index k) { If k != 0 Then { Print-longest-strictly-decreasing-subsequence1(PREV[0...n], PREV[k]) Print ak } } or alternatively: Print-longest-strictly-decreasing-subsequence2(array OPT[0...n], index k) { If k != 0 Then { // here it would be enough to say: let i be the index that gives us the maximum in: OPT[k] = 1 + (max over all i < k with ai > ak {OPT[i]}) but below we provide a detailed implementation of this statement // best-prev-so-far := 0 For i := 1 to k-1 do { If ai > ak Then { If (OPT[i] + 1) = OPT[k] Then { best-prev-so-far := i } } } Print-longest-strictly-decreasing-subsequence2(OPT[0...n], best-prev-so-far) Print ak } }Note that Print-longest-strictly-decreasing-subsequence1 and Print-longest-strictly-decreasing-subsequence2 are both O(n) since the longest strictly increasing subsequence has at most n elements and these procedures are called recursively once for each element of the subsequence.
Solution
We already proved by induction above that our recurrence is correct. Hence the only thing that remains to be proven is that our algorithm faithfully implements the recurrence. Given a j between 1 and n, note that the inner For loop ranges over the i's that are less than j, and for those for which ai > aj, it selects the one with maximum OPT[i], as the recurrence requires.
Solution
See the line by line runtime analysis above next to the algorithm. The total runtime is T(n)=O(n2), where n is the length of the input sequence.
A path from (0,0) to (n,m) is a sequence (0,0)=(a0,b0),(a1,b1),(a2,b2),...,(ak,bk)=(n,m) satisfying the following constraints:
You can only walk one block to the east (right) or one block to the north (up) at a time, and only on the avenues and on the streets (no diagonal moves allowed). For instance, a possible path to go from (0,0) to (2,3) is: (0,0), (0,1), (1,1), (1,2), (1,3), (2,3). The sequence (0,0), (1,1), (2,2), (2,3) is NOT a valid path, because it "cuts corners", and the sequence (0,0),(2,0),(2,3) is NOT a valid path because it skips intersections. Hence, for every i < k in the path:
Assume that there is exactly one path to go from a grid position to itself. The input-output description of this problem is:
Input: Two integers n and m, with n ≥ 0, m ≥ 0.
Output: The total number of different paths on the grid from (0,0) to (n,m) satisfying the two constraints above.
Solve this problem following the steps below.
Solution
First observe that Paths(n,m) = the total number of paths between (0,0) and (n,m) satisfying the two given constraints can be defined recursively as follows:Paths(n,m) = { 1, if n=0 or m=0, Paths(n-1,m) + Paths(n,m-1), otherwise }The subproblems to solve in this case is the number of paths to the two points immediately to the left and immediately to the bottom of the current grid point. The base case here is the first row and column where we know there can exist only one path as going down and left are not permitted. The correctness of this recursive definition is proved in a following subsection.Paths(i,j) -------------------------------------------------- n | 1 |n+1 | | | ... | | ... | | | -------------------------------------------------- n-1 | 1 | n | | | ... | | ... | | | -------------------------------------------------- ... | 1 | | | | ... | | ... | | | -------------------------------------------------- i | 1 |i+1 | | | ... | | ... | | | -------------------------------------------------- ... | 1 | | | | ... | | ... | | | -------------------------------------------------- 3 | 1 | 4 | 10 | 20 | ... | | ... | | | -------------------------------------------------- 2 | 1 | 3 | 6 | 10 | ... | | ... | | | -------------------------------------------------- 1 | 1 | 2 | 3 | 4 | ... |j+1 | ... | m |m+1 | -------------------------------------------------- 0 | 1 | 1 | 1 | 1 | ... | 1 | ... | 1 | 1 | -------------------------------------------------- 0 1 2 3 ... j ... m-1 m
Solution
Number-of-path-in-the-grid(n,m) { 2D array Paths[0...n,0...m] of integers // Initialize all elements in the first column as 1 // For i := 0 to n do { Paths[i,0] := 1 } // Initialize all elements in the first row as 1 // For j := 0 to m do { Paths[0,j] := 1 } // Use the recurrence for all other i's and j's in the matrix// For i := 1 to n do { For j := 1 to m do { Paths[i,j] := Paths[i-1,j] + Paths[i,j-1] } } return Paths[n,m] }Note that the order in which we are traversing the matrix guarantees that Paths[i-1,j] and Paths[i,j-1] already contain their correct values when they are used to calculate Paths[i,j].
Solution
Proof by induction on (k,l)
- Base Cases (k=0 or l=0): We can observe that the first row and column of the matrix holds correct values as there is always only one path to points on the grid at these locations, either straight up or straight right from (0,0).
- Inductive Step:
Inductive hypothesis (for any integer k,l): Assume that number of paths to (i,j) is correct for all i ≤ k and j ≤ l.Prove for (k+1,l+1): Given the constraints, there are only two ways to reach point (k+1,l+1), either from (k,l+1) or from (k+1,l). From (k,l+1) to (k+1,l+1) there is only one way, right, and the paths are the ones to (k,l+1) plus the point (k+1,l+1) therefore the number of paths stays the same. Similarly for the case of coming up from (k+1,l). Finally we observe that the paths from these two points are distinct because their last points are different. Thus the total number of paths to (k+1,l+1) is the sum of the number of paths to (k,l+1) and (k+1,l) and the algorithm is correct.
Solution
Initializing the first column takes O(n) time, initializing the first row takes O(m) time, and calculating the remaining entries of the matrix takes O(nxm) time, as each position on the grid must be calculated one by one until (m,n) is reached. Therefore the runtime of the whole algorithms is O(m*n).