• Post Reply Bookmark Topic Watch Topic
  • New Topic

Longest decreasing sub-array  RSS feed

 
Ranch Hand
Posts: 122
C++ Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
This is a bit tricky!
I have a given array of numbers, and I have to find the longest decreasing sub-array, but the thing is that the elements don't have to be next to each other!

For example, the longest decreasing sub-array 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?
 
Sheriff
Posts: 4289
127
Chrome Eclipse IDE Java Postgres Database VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Do you need to copy the array, or just put the next lower element in an array?
 
Kaspersky Ukshini
Ranch Hand
Posts: 122
C++ Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I need to count the longest sequence... that's what the function should return..
 
lowercase baba
Bartender
Posts: 12565
49
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
have you worked out - on paper - how to do it yourself?

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?
 
Kaspersky Ukshini
Ranch Hand
Posts: 122
C++ Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
fred rosenberger wrote:have you worked out - on paper - how to do it yourself?

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?


Dude, honestly! I have nooo clue! ):
 
fred rosenberger
lowercase baba
Bartender
Posts: 12565
49
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Kaspersky Ukshini
Ranch Hand
Posts: 122
C++ Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
1day left for my exam, brain is slowly stopping to work... Just what they like to do before exams lol!
 
Master Rancher
Posts: 2045
75
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
Kaspersky Ukshini
Ranch Hand
Posts: 122
C++ Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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...
 
fred rosenberger
lowercase baba
Bartender
Posts: 12565
49
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I wonder if recursion would work here...I honestly don't know...but..

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?
 
Piet Souris
Master Rancher
Posts: 2045
75
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
Knute Snortum
Sheriff
Posts: 4289
127
Chrome Eclipse IDE Java Postgres Database VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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?
     
    Kaspersky Ukshini
    Ranch Hand
    Posts: 122
    C++ Java
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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!!
     
    Kaspersky Ukshini
    Ranch Hand
    Posts: 122
    C++ Java
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Can't seem to be able to SORT the array and keep track of the indexes at the same time :/
    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.length-1 ..so the last member of b[] wont ever be reached..
     
    Knute Snortum
    Sheriff
    Posts: 4289
    127
    Chrome Eclipse IDE Java Postgres Database VI Editor
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    This is how I'd do it:

    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
     
    Kaspersky Ukshini
    Ranch Hand
    Posts: 122
    C++ Java
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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
     
    Sheriff
    Posts: 11494
    180
    Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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.
     
    Bartender
    Posts: 10575
    66
    Eclipse IDE Hibernate Ubuntu
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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 sub-array" in your list.
     
    Kaspersky Ukshini
    Ranch Hand
    Posts: 122
    C++ Java
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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....
     
    Bartender
    Posts: 1952
    7
    Eclipse IDE Java
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Ater you declare and initialize the index array at line 6 it contains only null references.
    You then dereference null inside your for-loop by invoking setValue() which results in a NullPointerException.
     
    Piet Souris
    Master Rancher
    Posts: 2045
    75
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    I must confess that my proposed solution did work for the example given, but it does not work in general,
    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
     
    Rancher
    Posts: 1090
    14
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    I have only tried an algorithm on paper so far. I mean no programming. Just some tree nodes and diagrams. Here's my algorithm.

    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 sub-tree node of the root. Store its parent as root. Calculate and store the depth of the sub-tree 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
    Rancher
    Posts: 1090
    14
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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.
     
    Winston Gutkowski
    Bartender
    Posts: 10575
    66
    Eclipse IDE Hibernate Ubuntu
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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
     
    Piet Souris
    Master Rancher
    Posts: 2045
    75
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    This Kaspersly with his poblems....

    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 subsequences-list:

    { {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:

     
    Chan Ag
    Rancher
    Posts: 1090
    14
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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 -156-I
    parent =546, depth =2, max depth node[] = {-165, 156-I}, max depth = 2
    165 also moves to the left cause it is larger than -156-I.



    Read -156 (Let this be -156-II)

    --> 546
    | |
    165 -156-I
    |
    -156-II parent =165, depth =3, max depth node[] = {156-II}, max depth = 3
    Can add to -156-I 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 -156-I
    | |
    -56 -156-II
    parent =165, depth =3, max depth node[] = {-56, 156-II}, max depth = 3




    Read -13

    --> 546
    | |
    165 -156-I
    | | |
    -13 -56 -156-II
    parent =165, depth =3, max depth node[] = {-13, -56, 156-II}, max depth = 3
    Add as the child of the left most node.


    Read 5

    --> 546
    | |
    165 -156-I
    | | | |
    5 -13 -56 -156-II
    parent =165, depth =3, max depth node[] = {5, -13, -56, 156-II}, 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, -156-II


    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
    Ranch Hand
    Posts: 122
    C++ Java
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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?
     
    Chan Ag
    Rancher
    Posts: 1090
    14
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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 for-loop 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[arrayLength-1] 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.
     
    Kaspersky Ukshini
    Ranch Hand
    Posts: 122
    C++ Java
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    But I'm doing it intentionaly, cause the Value variable holds he value, and I copy it by doing a[i], but the other value saves the INDEX of that value in the array, hence (i)
     
    Chan Ag
    Rancher
    Posts: 1090
    14
    • Likes 1
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    setValue and setIndex are instance methods. Instance methods are invoked on objects as follows.



    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?


     
    Chan Ag
    Rancher
    Posts: 1090
    14
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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.
     
    Piet Souris
    Master Rancher
    Posts: 2045
    75
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    hi Chan,

    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
     
    Chan Ag
    Rancher
    Posts: 1090
    14
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Ok, so if anybody is still interested in this, here's an implementation of the algorithm I was talking about a few days back. 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.






    Until someone finds a sequence that it will fail for.. :-)




     
    Chan Ag
    Rancher
    Posts: 1090
    14
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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 un-boxing 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.
     
    • Post Reply Bookmark Topic Watch Topic
    • New Topic
    Boost this thread!