{"id":4979,"date":"2019-05-03T06:00:00","date_gmt":"2019-05-03T04:00:00","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=4979"},"modified":"2019-05-19T19:23:53","modified_gmt":"2019-05-19T17:23:53","slug":"maxima-suma-de-los-segmentos","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/maxima-suma-de-los-segmentos\/","title":{"rendered":"M\u00e1xima suma de los segmentos"},"content":{"rendered":"<p>Un <strong>segmento<\/strong> de una lista xs es una sublista de xs formada por elementos consecutivos en la lista. El <strong>problema de la m\u00e1xima suma de segmentos<\/strong> consiste en dada una lista de n\u00fameros enteros calcular el m\u00e1ximo de las sumas de todos los segmentos de la lista. Por ejemplo, para la lista [-1,2,-3,5,-2,1,3,-2,-2,-3,6] la m\u00e1xima suma de segmentos es 7 que es la suma del segmento [5,-2,1,3] y para la lista [-1,-2,-3] es 0 que es la suma de la lista vac\u00eda.<\/p>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\"> \n   mss :: [Integer] -> Integer\n<\/pre>\n<p>tal que (mss xs) es la m\u00e1xima suma de los segmentos de xs. Por ejemplo,<\/p>\n<pre lang=\"text\"> \n   mss [-1,2,-3,5,-2,1,3,-2,-2,-3,6]  ==  7\n   mss [-1,-2,-3]                     ==  0\n   mss [1..500]                       ==  125250\n   mss [1..1000]                      ==  500500\n   mss [-500..3]                      ==  6\n   mss [-1000..3]                     ==  6\n<\/pre>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.List (inits,tails)\n\n-- 1\u00aa soluci\u00f3n\nmss :: [Integer] -> Integer\nmss = maximum . map sum . segmentos\n\n-- (segmentos xs) es la lista de los segmentos de xs. Por ejemplo,\n--    ghci> segmentos \"abc\"\n--    [\"\",\"a\",\"ab\",\"abc\",\"\",\"b\",\"bc\",\"\",\"c\",\"\"]\nsegmentos :: [a] -> [[a]]\nsegmentos = concat . map inits . tails\n\n-- 2\u00aa definici\u00f3n:\nmss2 :: [Integer] -> Integer\nmss2 = maximum . map (maximum . scanl (+) 0) . tails\n\n-- 3\u00aa definici\u00f3n:\nmss3 :: [Integer] -> Integer\nmss3 = maximum . map sum . concatMap tails . inits \n\n-- 4\u00aa definici\u00f3n\nmss4 :: [Integer] -> Integer\nmss4  = fst . foldr (\\x (b,a) -> (max (a+x) b, max 0 (a+x))) (0,0) \n\n-- 5\u00aa definici\u00f3n (con scanl):\nmss5 :: [Integer] -> Integer\nmss5 = maximum . scanl (\\a x -> max 0 a + x) 0\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n--    ghci> mss [1..500]\n--    125250\n--    (7.52 secs, 2022130824 bytes)\n--    \n--    ghci> mss2 [1..500]\n--    125250\n--    (0.01 secs, 10474956 bytes)\n--    \n--    ghci> mss3 [1..500]\n--    125250\n--    (0.98 secs, 841862016 bytes)\n--    \n--    ghci> mss4 [1..500]\n--    125250\n--    (0.01 secs, 552252 bytes)\n--    \n--    ghci> mss2 [1..1000]\n--    500500\n--    (0.06 secs, 54575712 bytes)\n--    \n--    ghci> mss3 [1..1000]\n--    500500\n--    (7.87 secs, 7061347900 bytes)\n--\n--    ghci> mss4 [1..1000]\n--    500500\n--    (0.01 secs, 549700 bytes)\n--    \n--    ghci> mss2 [1..2000]\n--    2001000\n--    (0.29 secs, 216424336 bytes)\n--    \n--    ghci> mss2 [1..5000]\n--    12502500\n--    (2.37 secs, 1356384840 bytes)\n--    \n--    ghci> mss4 [1..5000]\n--    12502500\n--    (0.02 secs, 1913548 bytes)\n--\n--    ghci> mss5 [1..5000]\n--    12502500\n--    (0.01 secs, 2886360 bytes)\n<\/pre>\n<h4>Pensamiento<\/h4>\n<blockquote><p>\nNubes, sol, prado verde y caser\u00edo<br \/>\nen la loma, revueltos. Primavera<br \/>\npuso en el aire de este campo fr\u00edo<br \/>\nla gracia de sus chopos de ribera.<\/p>\n<p>Antonio Machado\n<\/p><\/blockquote>\n","protected":false},"excerpt":{"rendered":"<p>Un segmento de una lista xs es una sublista de xs formada por elementos consecutivos en la lista. El problema de la m\u00e1xima suma de segmentos consiste en dada una lista de n\u00fameros enteros calcular el m\u00e1ximo de las sumas de todos los segmentos de la lista. Por ejemplo, para la lista [-1,2,-3,5,-2,1,3,-2,-2,-3,6] la m\u00e1xima&#8230;<\/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":[12,58,94,74,479,15,11,90,78,75],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4979"}],"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=4979"}],"version-history":[{"count":4,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4979\/revisions"}],"predecessor-version":[{"id":5032,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4979\/revisions\/5032"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=4979"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=4979"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=4979"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}