PHP longest increasing subsequence -

-

so there answers on here apply c trying in php, , in particular way.

i have array of numbers :

7, 2, 6, 3, 10

i want find longest increasing subsequence happens first in order given. example in case want result be:

2, 6, 10

and not 2, 3, 10.

what best way accomplish ?

okay, here's solution question yielding answer expect. basically, every element found start list , add items when greater last item in list far.

$input = array(7,2,6,3,10); $trial = array();  echo "input: "; print_r($input); echo "<br><br>\n";  foreach ($input $key => $value) {   // create new trial each starting point   // ------------------------------------------   $trial[$key][0] = $value;   echo "trial $key started<br>\n";    // process prior trials   // ------------------------   ($i = $key-1; $i >= 0; $i--)   {     echo "looking @ trial $i ";     $last = count($trial[$i]) - 1;     $lastval = $trial[$i][$last];     if ( $value > $lastval )     {       $trial[$i][] = $value;       echo "** added $value";     }     echo "<br>\n";   }   echo "<br>\n"; }  // find first longest trial // ------------------------ $longest = 0; foreach ($trial $key => $list) {   if ( count($list) > count($trial[$longest]) )     $longest = $key; }  echo "all trials:<br>\n"; print_r($trial); echo "<br><br>\n";  echo "first longest sequence:<br>\n"; print_r($trial[$longest]);

there of course things done differently if had large data sets. said, here "debug" output showing in action:

input: array ( [0] => 7 [1] => 2 [2] => 6 [3] => 3 [4] => 10 )   trial 0 started  trial 1 started ... looking @ trial 0   trial 2 started ... looking @ trial 1 ** added 6 ... looking @ trial 0   trial 3 started ... looking @ trial 2  ... looking @ trial 1  ... looking @ trial 0   trial 4 started ... looking @ trial 3 ** added 10 ... looking @ trial 2 ** added 10 ... looking @ trial 1 ** added 10 ... looking @ trial 0 ** added 10  trials: array (    [0] => array ( [0] => 7 [1] => 10 )    [1] => array ( [0] => 2 [1] => 6 [2] => 10 )    [2] => array ( [0] => 6 [1] => 10 )    [3] => array ( [0] => 3 [1] => 10 )    [4] => array ( [0] => 10 )  )   first longest sequence: array ( [0] => 2 [1] => 6 [2] => 10 )

Comments

Post a Comment

Popular posts from this blog

Fail to load namespace Spring Security http://www.springframework.org/security/tags -

-
i have problem namespace of spring security on xhtml page. don't understand why can't load uri, , have following issue: whitelabel error page application has no explicit mapping /error, seeing fallback. tue jul 21 16:58:12 utc 2015 there unexpected error (type=not found, status=404). please need help! possible uri has been changed? best regards you using incorrect namespace url. correct url http://www.springframework.org/schema/security the error page seeing spring source website since not recognize url. try visiting http://www.springsource.org/security/tags in browser update : spring security tags used in jsp page correct tag lib declaration is: <%@ taglib prefix="sec" uri="http://www.springframework.org/security/tags" %>
Read more

sql - MySQL query optimization using coalesce -

-
can explain me why second query faster first? (first 1 takes around 40 seconds, second 1 less 0.1) select releases.feature_code, releases.platform_id, version, release_date, general_available, uri, filesize, display_name, feature_name.full_name, if ((select exists(select 1 release_exceptions releases.feature_code = release_exceptions.feature_code , releases.platform_id = release_exceptions.platform_id , releases.version = release_exceptions.version) = 1), 1, 0) release_exceptions releases left outer join platform using(platform_id) left outer join feature_name using(feature_code) order version desc; ~~~ query 2 ------------------ ~~~ select feature_code, version, release_date, general_available, platform_id, uri, filesize, display_name, feature_name.full_name, coalesce(release_exceptions, 0) release_exceptions mus.releases left outer join ( select distinct feature_code, version, platform_id, 1 release_exceptions mus.release_exceptions ) release_exceptions using ...
Read more

unity3d - Unity local avoidance in user created world -

-
i'm using unity3d networked multiplayer online game have large complex 3d terrain scene forest, trees, cliff, hills, mountains, bounders, etc. players can build structures sort of minecraft, , put them anywhere in scene, or move them around anytime. aside human controlled players, there automated ai players , objects animals roaming around scene following path. the problem how make these automated ai players , animals, able navigate around static , dynamic player created structures, because path follow can blocked player created structures, or other players , other ai objects, cliffs etc. have find away around them or on track if tumble down off high cliff example. so made navmesh , used navagents, takes care of static, non moving objects, how make ai players navigate around each other , dynamic structures created players can number in hundreds? i thought of adding navmeshobstacle everything, result in being attached hundreds of objects since user created structures b...
Read more