I have a given array of numbers, and I have to find the longest decreasing subarray, but the thing is that the elements don't have to be next to each other!
For example, the longest decreasing subarray for this array:
546 156 165 156 56 13 5
is 3 (check the bold numbers)
Until now, I have nearly finished my code, but I have one problem...
The problem with this code is that it's not smart.. let's say I have:
100 500 90 80 70
Once it hits 500, none of the other if's with pass....
Any ideas how to avoid this?
an example is great, but it isn't really a spec. Do you think you could give those directions to a child and they could accurately compute it?
There are only two hard things in computer science: cache invalidation, naming things, and offbyone errors
Kaspersky Ukshini wrote:Dude, honestly! I have nooo clue! ):
So start thinking about it. sketch some examples. run through some scenarios. start with a small array, and work through it. Then try a slightly larger array. See if you can find a pattern.
Programming is more about teaching yourself how to think through a problem than writing code.
There are only two hard things in computer science: cache invalidation, naming things, and offbyone errors
but maybe you could sort the array, from high to low. Of course,
you loose the original positions, and that is very nasty,
but maybe there is a possibility to somehow keep the
original positions.
But even so, what use would all this be ? Hmm...
Greetz,
Piet
Piet Souris wrote:Well, it is too late now, for the upcoming exam and brainstop,
but maybe you could sort the array, from high to low. Of course,
you loose the original positions, and that is very nasty,
but maybe there is a possibility to somehow keep the
original positions.
But even so, what use would all this be ? Hmm...
Greetz,
Piet
I don't think sorting the list would somehow help...
We may get something similar to this in the exam, it doesn't hurt to learn a new idea, the thing is that in this case, i'm finding it hard to think of something...
546 156 165 156 56 13 5
so let's find the longest one in the array
546 156 165 156 56 13
If i know how long it is for that one, can I figure out if adding a 5 to the end improves the score?
There are only two hard things in computer science: cache invalidation, naming things, and offbyone errors
Kaspersky Ukshini wrote:
I don't think sorting the list would somehow help...
(...)
Well, take Fred's array:
546 156 165 156 56 13 5
and suppose that we sort it, keeping the original positions.
We get this:
Looking at this, anything that comes up? Take a special look at the original positions.
Greetz,
Piet
...Are you getting the idea?
All things are lawful, but not all things are profitable.
Knute Snortum wrote:Think about what you would actually do, remembering that the computer is forgetful and stupid.
I start at the first element I look for the next element that's lower I write down the elements that are in the subarray When I get to the end of the original array, I look at the subarray's length There might be another subarray, so I start at the second element of the original array I do the above steps again I check if my new subarray is longer than the other subarray
...Are you getting the idea?
That's what I already wrote before creating this topic, but it didn't work for all cases... cause the sub arrays doesn't have to be one after another.. I can start making my array from the first element, then jump to the 3rd, then 5th... JUST RIGHT.... that's what makes it harder, but nvm, I guess I found the solution...
Piet Souris wrote:Kaspersky Ukshini wrote:
I don't think sorting the list would somehow help...
(...)
Well, take Fred's array:
546 156 165 156 56 13 5
and suppose that we sort it, keeping the original positions.
We get this:
Looking at this, anything that comes up? Take a special look at the original positions.
Greetz,
Piet
Ohhh.... Nowwwwwwwwwwwwww I see!
After sorting it, I start looking for the longest INCREASING array (in the array of indexes)
LET ME GIVE IT A TRY RIGHT NOWWWWWWW!!
This is what I have up untill now:
I try printing the new array after the sort,but it's the other way around, plus there is a problem
cause the for loop only goes up until a.length1 ..so the last member of b[] wont ever be reached..
1) I need an array to hold the longest subarray
2) I need an array to hold the subarray I'm looking at
3) Start at the first element in the original array
4) Add the element to my temp array
5) Look at the next element
6) If it's less than the last element in the temp array, add it to the temp array
7) Do this for all elements in the array
8) If the temp array is longer than the longest subarray, copy the temp array to the longest
9) go to 3) but start at the second element
10) do steps 4 thru 8
11) now start at the third element in the original
12) continue like this until you get to the last element, or the longest array is longer than the remaining elements
13) return longest subarray
All things are lawful, but not all things are profitable.
Then I'm trying to convert the curent Array into my new one:
And NO LUCK! I'm getting this error when trying it: Exception in thread "main" java.lang.NullPointerException
Piet Souris wrote:But even so, what use would all this be ? Hmm...
I did some searching and apparently it does have practical uses. If you are interested, search terms include "longest increasing subsequence", "longest decreasing subsequence", "Pigeonhole Principle", "Erdős–Szekeres theorem", and "Dynamic Programming". As far as I could tell, one very familiar problem that is related to this kind of math is that of boarding people on a plane as efficiently as possible.
Practice only makes habit, only perfect practice makes perfect.
Practice mindfully by doing the right things and doing things right.— Junilu
[How to Ask Questions] [How to Answer Questions]
Kaspersky Ukshini wrote:I believe im close.. I've decided to use a new class of arrays, each holding the value and it's index.
You might also want to have a look at the Patience sorting algorithm, because it's a lot simpler to follow than the one for LIS (at least for a duffer like me). It also makes perfect sense that that kind of sort would be related to a "longest subsequence" solution.
Indeed, if you only need to return the length of the longest subsequence, I suspect it's also the quickest.
HIH
Winston
PS: It's maybe worth mentioning that there can be more than one "maximal subarray" in your list.
"Leadership is nature's way of removing morons from the productive flow"  Dogbert
Articles by Winston can be found here
Kaspersky Ukshini wrote:I believe im close.. I've decided to use a new class of arrays, each holding the value and it's index.
Then I'm trying to convert the curent Array into my new one:
And NO LUCK! I'm getting this error when trying it: Exception in thread "main" java.lang.NullPointerException
Guys, I belive I'm really close, I just need to know why am I getting this stupid error now? Maybe I'm missing a small detail somewhere, while compailing everything is ok....
You then dereference null inside your forloop by invoking setValue() which results in a NullPointerException.
Build a man a fire, and he'll be warm for a day. Set a man on fire, and he'll be warm for the rest of his life.
Besides, it would still be a bit awkward to get the longest sublist.
So I just wrote a much simpler solution, that does not involve any sorting. I have to go now,
but I'll show it later this afternoon.
Greetz,
Piet
1. Read one number ( each of those will make one or several tree nodes as we will see ) at a time.
2. For the first number, make it the root node. Store its depth. For the first node it'll be 1. Its parent is null. Store this node as one of the nodes with maximum depth in the maximum depth nodes' array.
3. Read the next number. For each number you read, traverse the tree from the root in the following way.
3.1 If the next number is smaller than or equal to the root number, add the number you read as a subtree node of the root. Store its parent as root. Calculate and store the depth of the subtree node you added. Update the maximum depth nodes' array.
3.2 If its larger than the root, start another tree with the node you read as the root. (There are some improvements possible as you traverse your trees  you can ignore some trees  but I will leave that up to you )
3.11 Now traverse each node at next level (root +1 depth ) referring to that as the current node. For this node also, if the number you have read is smaller than the current node, add the node you have read as its sub tree node. Store its depth and parent and so on...
At the end you have one or more elements in the maximum depth nodes' array. And you can traverse this way to get the sub array >
the leaf node with maximum depth > its parent > its parent's parent ..
I think this should work for all the cases.
Chan Ag wrote:
3.2 If its larger than the root, start another tree with the node you read as the root. (There are some improvements possible as you traverse your trees  you can ignore some trees  but I will leave that up to you )
I think a better wya to handle this is to create a dummy node with a really high number, say Integer.MAX_VALUE and make all root nodes, its children.
Yes, that should work.
Chan Ag wrote:I have only tried an algorithm on paper so far. I mean no programming. Just some tree nodes and diagrams.
I certainly think you're on the right lines; but I doubt that the structure involves just a single root (because there could be more than one "maximal" subsequence)  although, oddly enough, when I was trying to "visualise" it, I was thinking along exactly the same lines and using a heap  I suspect, however, that's it's only part of the solution, not the whole.
The Patience Sort ticks most of the boxes for me: It's simple, familiar, and it's also easy to follow how it's likely to be very strongly related to a "maximal sequence" problem.
Ain't programming fun?
Winston
The algorithm I came up with is easy, maybe along the way that Chan describes.
I'll give an example.
Suppose we have the array {4, 8, 2}.
And that we have a List of List<Integer>, called subsequences.
Now, start with the right most element, i.e. 2.
Compare this element to every List in subsequences. If the element
is larger than or equal to the first element of this List, add it
to the List. Finally, add the element to a new List, and add that List
to subsequences.
Then go to the next element to the left, do the same, et cetera,
until we had all elements.
We now have a list of ll subsequnces. Take the largesr in size
and we're done.
For array {4, 8, 2} we would get the following subsequenceslist:
{ {2} }
{ {8,2} , {2} , {8}}
{ {8,2}, {4, 2}, {2} , {8} , {4} }
And so the longest subsequence is either {8, 2} or {4, 2}
The only worry is that the number of LinkedLists is increasing at
an alarming rate, about 2^n, which is deadly for any algorithm.
Guess I'll have to do some extra study...
Here's the method:
Winston Gutkowski wrote:I doubt that the structure involves just a single root (because there could be more than one "maximal" subsequence
Thanks. Here's a work around that resulted in a refinement ( I think ).
Let's consider the following sequence.
546 156 165 156 56 13 5
Read 546
> 546 parent=null, depth=1, max depth node[] = {546}, max depth = 1
Read 156
> 546

156 parent = 546, depth =2, max depth node[] = {156}, max depth = 2
Read 165
> 546
 
165 156I
parent =546, depth =2, max depth node[] = {165, 156I}, max depth = 2
165 also moves to the left cause it is larger than 156I.
Read 156 (Let this be 156II)
> 546
 
165 156I

156II parent =165, depth =3, max depth node[] = {156II}, max depth = 3
Can add to 156I also but for roots of equal depth, pick the left most root cause that's the largest.
Add as the child of the left most node cause we can find any solution as long as it gives the longest sub sequence. This would greatly simplify the design cause we won't require a parent[].
Read 56
> 546
 
165 156I
 
56 156II
parent =165, depth =3, max depth node[] = {56, 156II}, max depth = 3
Read 13
> 546
 
165 156I
  
13 56 156II
parent =165, depth =3, max depth node[] = {13, 56, 156II}, max depth = 3
Add as the child of the left most node.
Read 5
> 546
 
165 156I
   
5 13 56 156II
parent =165, depth =3, max depth node[] = {5, 13, 56, 156II}, max depth = 3
Add as the child of the left most node.
So we get
546, 165, 5
546, 165, 13
546, 165, 56
546, 165, 156II
We can return the left most sequence here or (whichever we like ).
I am still working on Piet's solution for longer sequences.
Kaspersky Ukshini wrote:I believe im close.. I've decided to use a new class of arrays, each holding the value and it's index.
Then I'm trying to convert the curent Array into my new one:
And NO LUCK! I'm getting this error when trying it: Exception in thread "main" java.lang.NullPointerException
Guys, I think I found my way around it, I just need help with this detail.. what am I mising here?
Kaspersky Ukshini wrote:Kaspersky Ukshini wrote:
And NO LUCK! I'm getting this error when trying it: Exception in thread "main" java.lang.NullPointerException
Guys, I think I found my way around it, I just need help with this detail.. what am I mising here?
Sorry, I was just going on and on.
If you scroll up, you will see the following response by Jelle Klap.
Ater you declare and initialize the index array at line 6 it contains only null references.
You then dereference null inside your forloop by invoking setValue() which results in a NullPointerException.
Specifically index[0] is null. When you type the following,
you are only assigning index to an object that has several null references. In simple words, at this stage, Pair[0], Pair[1], Pair[arrayLength1] etc are all null.
So if you try to access index[0] without assigning it a Pair, you will get a NullPointerException. When you type
what you are doing is
1. Get index[i], say index[0] value.
2. On the object you get at index[0], invoke the setValue method with the argument a[i].
So 1 gives you a null. And at 2, you get a NullPointerException.
But if you had done this...
you wouldn't get a NullPointerException.
 1
Here obj has to be an object.
null is not an object. You cannot invoke an instance method on null.
If you execute the above code, you will get a NullPointerException cause you are trying to invoke an instance method on null.
If you execute the above code, you will not get a NullPointerException cause you are invoking an instance method on an object.
In your code example, I get it that you need to invoke the setValue and setIndex methods. But your index(i) is null.
Now do you see where the problem is?
Piet Souris wrote:
{ {2} }
{ {8,2} , {2} , {8}}
{ {8,2}, {4, 2}, {2} , {8} , {4} }
And so the longest subsequence is either {8, 2} or {4, 2}
The only worry is that the number of LinkedLists is increasing at
an alarming rate, about 2^n, which is deadly for any algorithm.
Guess I'll have to do some extra study...
Wow, Piet. Your program is cool. It works in all the cases. I could try it only today.
About the number of subsequences growing at an alarming rate, I have added one small refinement to your code. The idea is that we don't require the subsequence {8} in the second step cause we already have {8,2}. That is only step 1 of the refinement.
More refinements in this line are possible ( like you don't need to add the number to all the matching cases ) but I guess trickier ( for me because of the lack of the peace of mind because of the things going on in my lil space )
So just added this one step...
I am still working on various other suggestions by Winston and others and my own proposed solution. I might just take a little time in getting back though.
Thanks.
Edit : Changed the code.
thanks for this enormous work!
Indeed, I realised that I was storing way too many sublists, but since OP never reacted,
I didn't spend any more time on it, well, not on this site.
I showed this problem to a collegue of mine, who got interested and is having a look
at it now. Having just done the algorithmic course at Coursera, the next interesting
question is: what is the asymptotic behaviour of this algortihm, given the improvements
that you mention.
Running the program on an array of 50 random elements, run time and number of
sublists tend to vary, but it looks more like an O(n^3) thing than the dreaded O(2^n).
To be continued!
Greetz,
Piet
Until someone finds a sequence that it will fail for.. :)
Chan Ag wrote: I think it's asymptotic computational complexity is close to O(N log N) as we are only adding each node at one place only and we are examining only the applicable nodes.
No, it's O(N^2 log N).
Edit 
I think the nested class should really be a method local class inside the static method.
The above is too noisy. It should really be
The following
could actually be this or similar ( if you add the null check ) 
or better so since we have the unboxed value of i already, it's no point first boxing it and then unboxing it again. That parenthesis at the end has one more extra space which is inconsistent with the rest of the formatting.
The indentations created after breaking up long lines into shorter lines could also be made consistent.