Longest Increasing Subsequence

[mmiguel]

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 September 4, 2012 by mmiguel

[superprismatic]

I had to write a little program to get:

This 55-long sequence: 42 1318 2259 2339 5355 5709 9393 11299 12230 12641 14000 14289 17990 18498 18638 19218 21861 24351 25846 27141 28105 33535 35597 37723 38410 38833 38994 39295 45392 46268 46480 47318 47877 48856 50628 56087 57163 59481 60292 60868 65793 67511 67635 70066 75993 78289 79572 85182 87577 92362 94360 94963 95425 97491 97684

[mmiguel]

I had to write a little program to get:

This 55-long sequence: 42 1318 2259 2339 5355 5709 9393 11299 12230 12641 14000 14289 17990 18498 18638 19218 21861 24351 25846 27141 28105 33535 35597 37723 38410 38833 38994 39295 45392 46268 46480 47318 47877 48856 50628 56087 57163 59481 60292 60868 65793 67511 67635 70066 75993 78289 79572 85182 87577 92362 94360 94963 95425 97491 97684

Same one I got.

[mmiguel]

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 September 5, 2012 by mmiguel