Definir la funci\u00f3n<\/p>\n
\n longitudMayorSublistaCreciente :: Ord a => [a] -> Int\n<\/pre>\ntal que (longitudMayorSublistaCreciente xs) es la el m\u00e1ximo de las longitudes de las sublistas crecientes de xs. Por ejemplo,<\/p>\n
\n \u03bb> longitudMayorSublistaCreciente [3,2,6,4,5,1]\n 3\n \u03bb> longitudMayorSublistaCreciente [10,22,9,33,21,50,41,60,80]\n 6\n \u03bb> longitudMayorSublistaCreciente [0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15]\n 6\n \u03bb> longitudMayorSublistaCreciente [1..2000]\n 2000\n \u03bb> longitudMayorSublistaCreciente [2000,1999..1]\n 1\n \u03bb> import System.Random\n \u03bb> xs <- sequence [randomRIO (0,10^6) | _ <- [1..10^3]]\n \u03bb> longitudMayorSublistaCreciente2 xs\n 61\n \u03bb> longitudMayorSublistaCreciente3 xs\n 61\n<\/pre>\nNota<\/strong>: Se puede usar programaci\u00f3n din\u00e1mica para aumentar la eficiencia.<\/p>\nSoluciones<\/h4>\n\nimport Data.List (nub, sort)\nimport Data.Array (Array, (!), array, elems, listArray)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nlongitudMayorSublistaCreciente1 :: Ord a => [a] -> Int\nlongitudMayorSublistaCreciente1 =\n length . head . mayoresCrecientes\n\n-- (mayoresCrecientes xs) es la lista de las sublistas crecientes de xs\n-- de mayor longitud. Por ejemplo, \n-- \u03bb> mayoresCrecientes [3,2,6,4,5,1]\n-- [[3,4,5],[2,4,5]]\n-- \u03bb> mayoresCrecientes [3,2,3,2,3,1]\n-- [[2,3],[2,3],[2,3]]\n-- \u03bb> mayoresCrecientes [10,22,9,33,21,50,41,60,80]\n-- [[10,22,33,50,60,80],[10,22,33,41,60,80]]\n-- \u03bb> mayoresCrecientes [0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15]\n-- [[0,4,6,9,13,15],[0,2,6,9,13,15],[0,4,6,9,11,15],[0,2,6,9,11,15]]\nmayoresCrecientes :: Ord a => [a] -> [[a]]\nmayoresCrecientes xs =\n [ys | ys <- xss\n , length ys == m]\n where xss = sublistasCrecientes xs\n m = maximum (map length xss)\n\n-- (sublistasCrecientes xs) es la lista de las sublistas crecientes de\n-- xs. Por ejemplo,\n-- \u03bb> sublistasCrecientes [3,2,5]\n-- [[3,5],[3],[2,5],[2],[5],[]]\nsublistasCrecientes :: Ord a => [a] -> [[a]]\nsublistasCrecientes [] = [[]]\nsublistasCrecientes (x:xs) =\n [x:ys | ys <- yss, null ys || x < head ys] ++ yss\n where yss = sublistasCrecientes xs\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nlongitudMayorSublistaCreciente2 :: Ord a => [a] -> Int\nlongitudMayorSublistaCreciente2 xs =\n longitudSCM xs (sort (nub xs))\n \n-- (longitudSCM xs ys) es la longitud de la subsecuencia m\u00e1xima de xs e\n-- ys. Por ejemplo, \n-- longitudSCM \"amapola\" \"matamoscas\" == 4\n-- longitudSCM \"atamos\" \"matamoscas\" == 6\n-- longitudSCM \"aaa\" \"bbbb\" == 0\nlongitudSCM :: Eq a => [a] -> [a] -> Int\nlongitudSCM xs ys = (matrizLongitudSCM xs ys) ! (n,m)\n where n = length xs\n m = length ys\n\n-- (matrizLongitudSCM xs ys) es la matriz de orden (n+1)x(m+1) (donde n\n-- y m son los n\u00fameros de elementos de xs e ys, respectivamente) tal que\n-- el valor en la posici\u00f3n (i,j) es la longitud de la SCM de los i\n-- primeros elementos de xs y los j primeros elementos de ys. Por ejemplo,\n-- \u03bb> elems (matrizLongitudSCM \"amapola\" \"matamoscas\")\n-- [0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,2,2,2,2,2,2,\n-- 0,1,2,2,2,2,2,2,2,3,3,0,1,2,2,2,2,2,2,2,3,3,0,1,2,2,2,2,3,3,3,3,3,\n-- 0,1,2,2,2,2,3,3,3,3,3,0,1,2,2,3,3,3,3,3,4,4]\n-- Gr\u00e1ficamente,\n-- m a t a m o s c a s\n-- [0,0,0,0,0,0,0,0,0,0,0,\n-- a 0,0,1,1,1,1,1,1,1,1,1,\n-- m 0,1,1,1,1,2,2,2,2,2,2,\n-- a 0,1,2,2,2,2,2,2,2,3,3,\n-- p 0,1,2,2,2,2,2,2,2,3,3,\n-- o 0,1,2,2,2,2,3,3,3,3,3,\n-- l 0,1,2,2,2,2,3,3,3,3,3,\n-- a 0,1,2,2,3,3,3,3,3,4,4]\nmatrizLongitudSCM :: Eq a => [a] -> [a] -> Array (Int,Int) Int\nmatrizLongitudSCM xs ys = q\n where\n n = length xs\n m = length ys\n v = listArray (1,n) xs\n w = listArray (1,m) ys\n q = array ((0,0),(n,m)) [((i,j), f i j) | i <- [0..n], j <- [0..m]]\n where f 0 _ = 0\n f _ 0 = 0\n f i j | v ! i == w ! j = 1 + q ! (i-1,j-1)\n | otherwise = max (q ! (i-1,j)) (q ! (i,j-1))\n \n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nlongitudMayorSublistaCreciente3 :: Ord a => [a] -> Int\nlongitudMayorSublistaCreciente3 xs =\n maximum (elems (vectorlongitudMayorSublistaCreciente xs))\n\n-- (vectorlongitudMayorSublistaCreciente xs) es el vector de longitud n\n-- (donde n es el tama\u00f1o de xs) tal que el valor i-\u00e9simo es la longitud\n-- de la sucesi\u00f3n m\u00e1s larga que termina en el elemento i-\u00e9simo de\n-- xs. Por ejemplo, \n-- \u03bb> vectorlongitudMayorSublistaCreciente [3,2,6,4,5,1]\n-- array (1,6) [(1,1),(2,1),(3,2),(4,2),(5,3),(6,1)]\nvectorlongitudMayorSublistaCreciente :: Ord a => [a] -> Array Int Int\nvectorlongitudMayorSublistaCreciente xs = v\n where v = array (1,n) [(i,f i) | i <- [1..n]]\n n = length xs\n w = listArray (1,n) xs\n f 1 = 1\n f i | null ls = 1\n | otherwise = 1 + maximum ls\n where ls = [v ! j | j <-[1..i-1], w ! j < w ! i]\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- \u03bb> longitudMayorSublistaCreciente1 [1..20]\n-- 20\n-- (4.60 secs, 597,014,240 bytes)\n-- \u03bb> longitudMayorSublistaCreciente2 [1..20]\n-- 20\n-- (0.03 secs, 361,384 bytes)\n-- \u03bb> longitudMayorSublistaCreciente3 [1..20]\n-- 20\n-- (0.03 secs, 253,944 bytes)\n-- \n-- \u03bb> longitudMayorSublistaCreciente2 [1..2000]\n-- 2000\n-- (8.00 secs, 1,796,495,488 bytes)\n-- \u03bb> longitudMayorSublistaCreciente3 [1..2000]\n-- 2000\n-- (5.12 secs, 1,137,667,496 bytes)\n-- \n-- \u03bb> longitudMayorSublistaCreciente1 [1000,999..1]\n-- 1\n-- (0.95 secs, 97,029,328 bytes)\n-- \u03bb> longitudMayorSublistaCreciente2 [1000,999..1]\n-- 1\n-- (7.48 secs, 1,540,857,208 bytes)\n-- \u03bb> longitudMayorSublistaCreciente3 [1000,999..1]\n-- 1\n-- (0.86 secs, 160,859,128 bytes)\n-- \n-- \u03bb> longitudMayorSublistaCreciente1 (show (2^300))\n-- 10\n-- (7.90 secs, 887,495,368 bytes)\n-- \u03bb> longitudMayorSublistaCreciente2 (show (2^300))\n-- 10\n-- (0.04 secs, 899,152 bytes)\n-- \u03bb> longitudMayorSublistaCreciente3 (show (2^300))\n-- 10\n-- (0.04 secs, 1,907,936 bytes)\n-- \n-- \u03bb> longitudMayorSublistaCreciente2 (show (2^6000))\n-- 10\n-- (0.06 secs, 9,950,592 bytes)\n-- \u03bb> longitudMayorSublistaCreciente3 (show (2^6000))\n-- 10\n-- (3.46 secs, 686,929,744 bytes)\n-- \n-- \u03bb> import System.Random\n-- (0.00 secs, 0 bytes)\n-- \u03bb> xs <- sequence [randomRIO (0,10^6) | _ <- [1..10^3]]\n-- (0.02 secs, 1,993,032 bytes)\n-- \u03bb> longitudMayorSublistaCreciente2 xs\n-- 61\n-- (7.73 secs, 1,538,771,392 bytes)\n-- \u03bb> longitudMayorSublistaCreciente3 xs\n-- 61\n-- (1.04 secs, 212,538,648 bytes)\n-- \u03bb> xs <- sequence [randomRIO (0,10^6) | _ <- [1..10^3]]\n-- (0.03 secs, 1,993,032 bytes)\n-- \u03bb> longitudMayorSublistaCreciente2 xs\n-- 57\n-- (7.56 secs, 1,538,573,680 bytes)\n-- \u03bb> longitudMayorSublistaCreciente3 xs\n-- 57\n-- (1.05 secs, 212,293,984 bytes)\n<\/pre>\n","protected":false},"excerpt":{"rendered":"Definir la funci\u00f3n longitudMayorSublistaCreciente :: Ord a => [a] -> Int tal que (longitudMayorSublistaCreciente xs) es la el m\u00e1ximo de las longitudes de las sublistas crecientes de xs. Por ejemplo, \u03bb> longitudMayorSublistaCreciente [3,2,6,4,5,1] 3 \u03bb> longitudMayorSublistaCreciente [10,22,9,33,21,50,41,60,80] 6 \u03bb> longitudMayorSublistaCreciente [0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15] 6 \u03bb> longitudMayorSublistaCreciente [1..2000] 2000 \u03bb> longitudMayorSublistaCreciente [2000,1999..1] 1 \u03bb> import System.Random \u03bb> xs…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[4],"tags":[250,8,286,245,71,28,72,10,42,15,24,141,11,6,14],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/5868"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/comments?post=5868"}],"version-history":[{"count":3,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/5868\/revisions"}],"predecessor-version":[{"id":5895,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/5868\/revisions\/5895"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=5868"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=5868"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=5868"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}