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
