IM sorry I do not understand: For array A of length N, and for an integer k < N: -- By k do you mean value of k or position of k in the list?
L(A, k) is the length of the longest increasing subsequence of the prefix of A with length k, where that subsequence needs to include the k'th element too. What is L? This L function tries to capture the idea of having a *partial* solution that involves a portion of the array A. Why is it helpful? Because of two crucial things: 1. If we know L(A, 1), L(A, 2), ... all the way to L(A, N), then we can just look at the maximum value of those pieces. That's going to be a solution to the general problem. -- By maximum value do you mean I have to sum up the values in the list? Why? 2. For a subproblem L(A, k), if we know the values for L(A, 1), L(A, 2), ... , L(A, k-1), then we can compute L(A, k) by looking at those other subproblems: the result of L(A, k) is related to them. -- How do we find those subproblems? And then how do you relate them to the main problem? Can you please explain more in details? Thank you so much Monika ---------- Original Message ---------- From: Danny Yoo <d...@hashcollision.org> To: Alan Gauld <alan.ga...@yahoo.co.uk> Cc: "monik...@netzero.net" <monik...@netzero.net>, tutor <tutor@python.org> Subject: Re: [Tutor] python programmin problem Date: Sat, 23 Jul 2016 00:13:36 -0700 On Thu, Jul 21, 2016 at 11:30 PM, Alan Gauld via Tutor <tutor@python.org> wrote: > > Forwarding to list. Please use reply-all when responding to tutor messages. > > As Danny suggested this is quite a complex problem. I wasn't sure whether > it was just the programming or the bigger algorithm issue you were stuck on. [warning: large message ahead.] This problem is unfortunately not something you can just code by trying to hack it till it works. At this level of difficulty, these kinds of problems are *not* easy: they require some understanding of fundamentals in algorithms, not Python. That is, the actual coding of this is not the hard part. A direct solution to this problem is a couple of lines and involves nothing more loops and arrays. The difficulty is understanding how to use solutions of sub-problems toward the general large problem. I should state this more strongly: trying to hack the solution is not going to work. I have to ignore the code presented in this thread because there's very little to preserve. The approach of trying to look at only the very previous element is simply not viable. The most direct approach I know to do this is by talking about this in terms of subproblems. Here is a sketch of the idea: Let's put on our magical thinking cap, and say that we'd like to design a function L(A, m) with the following funny property: For array A of length N, and for an integer k < N: L(A, k) is the length of the longest increasing subsequence of the prefix of A with length k, where that subsequence needs to include the k'th element too. What is L? This L function tries to capture the idea of having a *partial* solution that involves a portion of the array A. Why is it helpful? Because of two crucial things: 1. If we know L(A, 1), L(A, 2), ... all the way to L(A, N), then we can just look at the maximum value of those pieces. That's going to be a solution to the general problem. 2. For a subproblem L(A, k), if we know the values for L(A, 1), L(A, 2), ... , L(A, k-1), then we can compute L(A, k) by looking at those other subproblems: the result of L(A, k) is related to them. How so? ------------------------------------------------------------------- As a concrete example, consider a list A = [5, 8, 6, 7]. * What is L(A, 1)? We want the length of the longest subsequence of the prefix [5] that includes the 5. And that's just 1. L(A, 1) = 1. That is, we're starting from scratch: we can't do better than just pick the 5 as the start of our subsequence. Since our subsequence just has [5], that's a subsequence of length 1. * What is L(A, 2)? We want the length of the longest subsequence of the prefix [5, 8] that includes the 8. Why does knowing L(A, 1) help us? Because we know L(A, 1) is 1. What does that mean? We look at L(A, 1) to see if maybe we can pick the subsequence that it is measuring, and augment it. We know L(A, 1) is the length of the longest sequence that ends up including the first element of A, so we know that subsequence ends with a [... 5]. And we can extend that subsequence so it look like [..., 5, 8]. And we know that such an extension will be of length 2. Can we do any better? There are no other subproblems, so no. That is, L(A, 2) = 2. * What is L(A, 3)? We want the length of the longest subsequence of the prefix [5, 8, 6] that includes the 6. We look at L(A, 1): can we just extend [..., 5] with a 6? Yes, and that gives us 2 as a possible answer for L(A, 3). Why 2? Because L(A, 1) = 1, and if we extend the subsequence measured by L(A, 1), we make it one element longer, so 1 + 1 = 2. Can we do better? We look at L(A, 2): can we just extend [..., 8] with a 6? No. Ok, so L(A, 3) = 2. * What is L(A, 4)? We want the length of the longest subsequence of the prefix [5, 8, 6, 7] that includes the 7. We look at L(A, 1):. Can we just extend [..., 5] with a 7? Yes, and that gives us 2 as a possible answer for L(A, 4). Can we do better? We look at L(A, 2). Can we just extend [..., 8] with a 7? No. Can we do better? We look at L(A, 3). Can we just extend [..., 6] with a 7? Yes, and that gives us 3 as a possible answer for L(A, 4). Why 3? Because L(A, 3) = 2, and if we extend the subsequence measured by L(A, 3), we make it one element longer, so 2+1 = 3. Ok, we've got L(A, 1), L(A, 2), L(A, 3), and L(A, 4). Which one was the largest? 3. What's the subsequence that's of length 3? We know it's [5, 6, 7], and that's length 3, so that seems to match. So the length of the longest subsequence of the whole A is 3. ------------------------------------------------------------------- Generalizing: when we're looking for a solution for L(A, k), we can look at the prior values L(A, 1), L(A, 2), ... L(A, k), because those represent the lengths of other longest subsequences that we can extend by including the k'th element. But we've got to look to see if the extension is valid ifrst, and that requires looking at elements of A at the respective positions. Once we do this, we can then pick the one that gives us the longest valid extension. -------------------------------------------------------------------- You need to try to do similar reasoning for smaller examples to convince yourself that this approach works in general. For example, try it on the input [5, 8, 3]. . This is the kind of process that's expected when solving this class of problems. If you haven't seen this style of attacking a problem by relating to smaller subproblems, then we strongly urge you to please talk with your professor or study group. _______________________________________________ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor ____________________________________________________________ Affordable Wireless Plans Set up is easy. Get online in minutes. Starting at only $9.95 per month! www.netzero.net?refcd=nzmem0216 _______________________________________________ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor