Jump to content


Welcome to BrainDen.com - Brain Teasers Forum

Welcome to BrainDen.com - Brain Teasers Forum. Like most online communities you must register to post in our community, but don't worry this is a simple free process. To be a part of BrainDen Forums you may create a new account or sign in if you already have an account.
As a member you could start new topics, reply to others, subscribe to topics/forums to get automatic updates, get your own profile and make new friends.

Of course, you can also enjoy our collection of amazing optical illusions and cool math games.

If you like our site, you may support us by simply clicking Google "+1" or Facebook "Like" buttons at the top.
If you have a website, we would appreciate a little link to BrainDen.

Thanks and enjoy the Den :-)
Guest Message by DevFuse
 

Photo
- - - - -

Longest Increasing Subsequence


  • Please log in to reply
3 replies to this topic

#1 mmiguel

mmiguel

    Advanced Member

  • Members
  • PipPipPip
  • 134 posts
  • Gender:Not Telling

Posted 04 September 2012 - 01:35 AM

This may need the help of a computer.

Find the longest increasing subsequence of the following 1000 distinct integers.

For a sequence of distinct integers, x_1, x_2, ... x_n,
A subsequence of length k is an ordered group of integers from the above sequence x_i_1, x_i_2, ... x_i_k, which retains order from original sequence, i.e. i_1 < i_2 < ... < i_k.
Note this does not require anything to be consecutive.

An increasing subsequence is a subsequence that increases i.e. x_i_1 < x_i_2 < ... < x_i_k.

The longest increasing subsequence is the increasing subsequence with the longest length.

Good luck!


75004, 56991, 47082, 19635, 42, 89416, 84822, 18366, 8364, 40699, 23120, 7706, 33866, 37458, 86632, 81435, 52136, 3743, 99783, 54643, 62785, 53908, 22213, 85048, 58919, 16044, 71291, 11096, 59245, 56845, 74161, 56308, 23503, 19719, 29656, 86735, 44249, 50773, 14885, 34940, 35646, 3160, 60678, 41299, 59937, 63207, 29450, 89997, 58911, 72711, 64902, 68401, 16899, 4501, 1318, 39683, 66480, 38689, 35095, 80701, 44054, 92075, 33988, 84671, 77537, 8839, 79523, 97433, 8391, 92759, 24585, 89033, 92547, 96080, 26073, 25745, 87630, 73072, 3266, 93177, 93474, 28759, 41164, 2305, 13755, 75280, 2259, 79239, 15564, 27736, 54375, 46184, 3033, 68422, 206, 83226, 8360, 78954, 17911, 37711, 92022, 39688, 66587, 16693, 2339, 92043, 58894, 94182, 93325, 55418, 59121, 57753, 83252, 53228, 68183, 23544, 89165, 57872, 57644, 24952, 22655, 23713, 61634, 68070, 58226, 29503, 71317, 70499, 61070, 9764, 62770, 13522, 36014, 65168, 20298, 43841, 34994, 25063, 86785, 52194, 70311, 81444, 11232, 88436, 83271, 50301, 18761, 29847, 6141, 57699, 61747, 65283, 79193, 80955, 36628, 70822, 66120, 77500, 80812, 18704, 24394, 62520, 15265, 68518, 57144, 69129, 89394, 63356, 5355, 78864, 43417, 22656, 27494, 77278, 19023, 96999, 73467, 68113, 76376, 70153, 95341, 26452, 60308, 25357, 808, 87635, 11781, 92324, 9737, 5709, 2360, 9393, 26000, 5525, 66538, 46059, 11299, 68012, 94219, 20545, 49775, 12230, 38787, 42187, 13954, 79224, 38397, 12641, 18491, 27646, 60193, 43950, 80949, 90488, 93327, 29476, 69194, 83723, 18315, 9124, 82261, 56942, 49866, 14000, 90370, 3396, 77977, 85948, 68664, 60297, 84844, 53267, 67547, 54998, 82753, 3496, 38235, 8761, 3958, 69268, 69156, 24947, 78750, 46293, 23810, 52238, 19946, 44903, 81118, 76939, 82285, 84902, 74667, 26038, 63344, 26064, 51882, 62396, 92332, 71340, 57031, 68813, 21653, 11169, 45501, 3257, 76192, 97946, 20814, 35897, 14289, 91788, 71387, 44558, 83180, 2647, 93610, 96951, 47531, 27440, 47218, 11286, 52915, 93140, 3246, 3433, 39289, 33040, 87405, 79325, 71823, 50094, 30705, 17990, 85064, 81540, 59265, 27807, 62779, 55603, 18992, 59418, 23469, 88774, 23189, 45086, 60996, 10533, 33384, 31671, 42096, 39391, 96782, 84041, 66203, 25541, 37887, 97948, 42245, 93682, 8423, 70414, 53152, 69561, 66511, 28690, 73268, 45783, 59991, 43532, 79262, 3537, 11824, 61333, 94830, 64856, 53646, 59199, 89931, 11691, 86182, 91830, 67544, 51331, 77435, 68866, 44869, 44133, 87167, 22813, 59897, 18498, 46753, 56559, 25556, 86163, 7, 99422, 92240, 88075, 36062, 94790, 63981, 31121, 93567, 21313, 18638, 70913, 10363, 81772, 89573, 19218, 82300, 67325, 68429, 94999, 47454, 271, 78843, 7864, 37438, 13609, 43965, 80713, 56972, 48789, 8213, 52201, 27, 99917, 90747, 85131, 85191, 88148, 68718, 21861, 48539, 76163, 61870, 72247, 6328, 77510, 85161, 25671, 72616, 1494, 69915, 6554, 545, 95768, 37429, 66219, 86730, 47812, 69958, 15057, 95984, 82951, 85727, 4871, 49055, 2670, 87984, 52839, 1390, 24351, 34921, 28927, 8073, 4050, 70171, 85043, 3888, 84466, 27613, 52344, 81876, 41264, 75722, 13727, 78878, 2151, 31297, 19708, 58176, 25846, 47132, 58684, 15779, 43179, 96985, 94527, 50770, 48819, 64608, 51588, 4126, 2349, 11697, 40969, 23669, 18253, 33731, 48139, 88237, 70099, 27141, 55890, 61625, 71161, 73823, 7413, 84892, 8336, 20848, 68198, 44231, 67412, 52152, 99178, 42452, 35439, 63439, 90645, 99836, 39082, 20436, 10443, 7534, 7308, 56095, 78778, 80929, 50848, 4734, 81855, 71427, 49395, 25020, 66462, 13295, 24367, 24077, 29723, 79883, 95739, 51912, 8202, 55787, 71631, 90593, 7549, 52322, 28105, 75281, 94227, 85491, 86745, 14201, 71018, 33535, 35597, 93171, 16611, 39463, 32185, 3766, 41114, 10756, 89390, 48987, 19558, 78031, 61062, 99330, 66976, 51138, 96108, 4417, 13389, 19419, 9359, 97062, 26579, 72817, 12401, 83340, 46928, 20740, 54991, 3744, 28769, 64999, 9641, 17251, 1117, 4656, 37723, 38410, 68597, 72258, 19024, 52105, 75443, 67881, 41368, 39165, 42547, 82381, 9538, 40546, 7034, 56061, 26456, 50629, 53180, 1819, 22409, 3833, 11855, 58669, 27778, 10663, 79657, 38833, 12714, 46197, 21632, 10778, 21247, 38994, 25892, 44301, 55788, 3232, 91229, 75892, 50093, 47105, 59594, 32454, 18488, 25106, 43564, 97242, 28572, 25663, 70039, 91706, 97061, 23416, 29455, 47052, 10566, 12143, 26216, 76453, 29371, 52863, 67569, 58398, 19473, 80787, 57301, 6821, 19269, 14382, 85683, 55428, 1711, 87501, 13629, 33064, 69783, 77117, 43023, 64628, 20502, 93203, 82528, 74892, 26203, 88761, 88038, 46496, 35584, 94159, 64423, 61958, 66594, 53304, 10172, 76705, 56290, 35347, 53466, 15360, 47748, 76041, 32612, 56078, 54272, 78187, 39832, 9834, 16764, 65969, 20091, 66682, 98199, 86121, 8412, 33017, 61921, 63269, 51421, 82766, 39295, 81130, 5731, 46723, 38277, 46094, 45392, 26417, 77154, 92349, 3104, 28788, 97644, 86701, 77673, 93956, 10113, 6253, 46268, 75770, 77218, 7318, 82262, 43967, 64407, 78133, 46480, 12561, 22850, 16789, 16129, 66381, 23275, 86098, 78141, 96486, 22257, 46046, 43321, 81526, 39600, 70788, 75764, 31406, 9363, 94082, 68919, 73381, 12959, 67194, 42059, 95390, 56476, 91971, 47480, 7679, 951, 47318, 31896, 79076, 40517, 83064, 45687, 76070, 98892, 75615, 30432, 44716, 42029, 92085, 11992, 47877, 31085, 48856, 62469, 25805, 58986, 41969, 66607, 9650, 19730, 60892, 1891, 45233, 64014, 27531, 50628, 58999, 25691, 22573, 18814, 56087, 16281, 43278, 70701, 88716, 72662, 8998, 37160, 57163, 53597, 75790, 47438, 13103, 18399, 16465, 85715, 84749, 36760, 59481, 68031, 73626, 39941, 99556, 48286, 631, 22187, 20672, 60292, 13294, 55728, 42836, 60868, 57542, 65793, 67511, 80985, 22778, 3118, 67635, 62144, 537, 60887, 36394, 18717, 1329, 15206, 51603, 76202, 70066, 89487, 58899, 16514, 14226, 83030, 75993, 57830, 6729, 12395, 60987, 6978, 78289, 69405, 81122, 65066, 38164, 4680, 23383, 68997, 39291, 74106, 79572, 66198, 45202, 63754, 314, 61671, 85182, 29085, 70065, 79251, 51533, 27482, 21828, 24281, 98349, 17770, 47250, 87577, 73692, 68513, 11779, 84333, 22388, 92362, 41332, 20732, 42300, 17794, 39118, 98820, 27239, 57836, 61284, 7438, 94360, 21918, 92132, 16495, 76257, 72770, 98012, 56210, 94963, 13159, 64244, 47544, 86650, 85170, 73094, 84045, 87091, 11321, 30070, 24693, 30661, 10754, 65326, 95425, 71842, 86623, 69595, 18271, 53478, 66871, 65051, 51952, 61675, 56902, 38295, 93632, 1422, 67653, 3823, 39370, 37089, 85086, 21651, 34279, 50938, 21553, 66385, 22009, 80771, 49446, 78005, 98473, 24097, 60795, 39608, 48406, 8878, 23676, 93051, 40222, 48557, 76866, 92950, 14235, 47887, 72266, 17844, 84939, 56057, 70925, 25003, 87227, 49456, 51275, 73926, 75899, 21522, 27319, 27803, 37639, 48036, 13770, 64662, 50456, 47995, 2545, 4404, 99938, 27323, 49744, 50772, 61467, 3524, 85916, 3089, 11310, 73870, 61462, 32734, 14100, 55427, 6236, 97491, 61637, 62180, 18231, 10939, 40795, 39273, 37057, 80598, 97684, 38541, 5465, 68441, 31373, 45814, 10120, 20062, 51881, 74221, 2725, 23346, 35000, 61254, 77930, 273, 50381

Edited by mmiguel, 04 September 2012 - 01:41 AM.

  • 0

#2 superprismatic

superprismatic

    Not just Prismatic

  • Moderator
  • PipPipPipPip
  • 1281 posts
  • Gender:Male

Posted 04 September 2012 - 07:35 PM

I had to write a little program to get:
Spoiler for answer

  • 0

#3 mmiguel

mmiguel

    Advanced Member

  • Members
  • PipPipPip
  • 134 posts
  • Gender:Not Telling

Posted 05 September 2012 - 04:45 AM

I had to write a little program to get:

Spoiler for answer

Same one I got. :)
  • 0

#4 mmiguel

mmiguel

    Advanced Member

  • Members
  • PipPipPip
  • 134 posts
  • Gender:Not Telling

Posted 05 September 2012 - 06:22 AM

Same one I got. :)


I generated the 1000 numbers in the following manner:

While I have less than 1000 numbers{
Pick a random whole number between 1 and 100000
If I don't already have this number, add it to my list
}

In this case, the longest increasing subsequence was length 55.

Challenge:
Can you determine the probability distribution of the length of longest increasing subsequences for M distinct numbers ranging from 1 to N (generated in the way described above)?
(Cumulative or probability mass function would be good).
I have no idea what the answer to this might look like, but I'm curious if it would turn out to be a common distribution, or perhaps a very uncommon one.

If we can't come up with a good theory, we can get some empirical data.
Perhaps from empirical data, we could come up with a theory!!

Edited by mmiguel, 05 September 2012 - 06:23 AM.

  • 0




0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users