{"id":2243,"date":"2016-03-17T06:00:40","date_gmt":"2016-03-17T04:00:40","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=2243"},"modified":"2016-05-01T19:59:47","modified_gmt":"2016-05-01T17:59:47","slug":"maxima-suma-de-elementos-consecutivos","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/maxima-suma-de-elementos-consecutivos\/","title":{"rendered":"M\u00e1xima suma de elementos consecutivos"},"content":{"rendered":"<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   sumaMaxima :: [Integer] -> Integer\n<\/pre>\n<p>tal que (sumaMaxima xs) es el valor m\u00e1ximo de la suma de elementos consecutivos de la lista xs. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   sumaMaxima []             ==  0 \n   sumaMaxima [2,-2,3,-3,4]  ==  4\n   sumaMaxima [-1,-2,-3]     ==  0\n   sumaMaxima [2,-1,3,-2,3]  ==  5\n   sumaMaxima [1,-1,3,-2,4]  ==  5\n   sumaMaxima [2,-1,3,-2,4]  ==  6\n   sumaMaxima [1..10^6]      ==  500000500000\n<\/pre>\n<p>Comprobar con QuickCheck que<\/p>\n<pre lang=\"text\">\n   sumaMaxima xs == sumaMaxima (reverse xs)\n<\/pre>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.List (inits, tails)\nimport Test.QuickCheck\n\n-- 1\u00aa definici\u00f3n\n-- =============\n\nsumaMaxima1 :: [Integer] -> Integer\nsumaMaxima1 [] = 0\nsumaMaxima1 xs =\n    maximum (0 : map sum [sublista xs i j | i <- [0..length xs - 1],\n                                            j <- [i..length xs - 1]])\n\nsublista :: [Integer] -> Int -> Int -> [Integer]\nsublista xs i j =\n    [xs!!k | k <- [i..j]]\n\n-- 2\u00aa definici\u00f3n\n-- =============\n\nsumaMaxima2 :: [Integer] -> Integer\nsumaMaxima2 [] = 0\nsumaMaxima2 xs = sumaMaximaAux 0 0 xs\n    where m = maximum xs\n\nsumaMaximaAux :: Integer -> Integer -> [Integer] -> Integer\nsumaMaximaAux m v [] = max m v\nsumaMaximaAux m v (x:xs)\n    | x >= 0    = sumaMaximaAux m (v+x) xs\n    | v+x > 0   = sumaMaximaAux (max m v) (v+x) xs\n    | otherwise = sumaMaximaAux (max m v) 0 xs\n\n-- 3\u00aa definici\u00f3n\n-- =============\n\nsumaMaxima3 :: [Integer] -> Integer\nsumaMaxima3 [] = 0\nsumaMaxima3 xs = maximum (map sum (segmentos xs))\n\n-- (segmentos xs) es la lista de los segmentos de xs. Por ejemplo \n--    segmentos \"abc\"  ==  [\"\", \"a\",\"ab\",\"abc\",\"b\",\"bc\",\"c\"]\nsegmentos :: [a] -> [[a]]\nsegmentos xs =\n    [] : concat [tail (inits ys) | ys <- init (tails xs)]\n\n-- 4\u00aa definici\u00f3n\n-- =============\n\nsumaMaxima4 :: [Integer] -> Integer\nsumaMaxima4 [] = 0\nsumaMaxima4 xs = \n    maximum (concat [scanl (+) 0 ys | ys <- tails xs])\n\n-- Comprobaci\u00f3n\n-- ============\n\n-- La propiedad es\nprop_sumaMaxima :: [Integer] -> Bool\nprop_sumaMaxima xs =\n    sumaMaxima2 xs == n &&\n    sumaMaxima3 xs == n &&\n    sumaMaxima4 xs == n\n    where n = sumaMaxima1 xs\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_sumaMaxima\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n--    \u03bb> let n = 10^2 in sumaMaxima1 [-n..n] \n--    5050\n--    (2.10 secs, 390,399,104 bytes)\n--    \u03bb> let n = 10^2 in sumaMaxima2 [-n..n] \n--    5050\n--    (0.02 secs, 0 bytes)\n--    \u03bb> let n = 10^2 in sumaMaxima3 [-n..n] \n--    5050\n--    (0.27 secs, 147,705,184 bytes)\n--    \u03bb> let n = 10^2 in sumaMaxima4 [-n..n] \n--    5050\n--    (0.04 secs, 11,582,520 bytes)\n\nprop_inversa :: [Integer] -> Bool\nprop_inversa xs =\n    sumaMaxima2 xs == sumaMaxima2 (reverse xs)\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Definir la funci\u00f3n sumaMaxima :: [Integer] -> Integer tal que (sumaMaxima xs) es el valor m\u00e1ximo de la suma de elementos consecutivos de la lista xs. Por ejemplo, sumaMaxima [] == 0 sumaMaxima [2,-2,3,-3,4] == 4 sumaMaxima [-1,-2,-3] == 0 sumaMaxima [2,-1,3,-2,3] == 5 sumaMaxima [1,-1,3,-2,4] == 5 sumaMaxima [2,-1,3,-2,4] == 6 sumaMaxima [1..10^6] ==&#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":[8,12,285,74,28,10,83,15,11,6,45,75],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/2243"}],"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=2243"}],"version-history":[{"count":4,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/2243\/revisions"}],"predecessor-version":[{"id":2384,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/2243\/revisions\/2384"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=2243"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=2243"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=2243"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}