Menu Close

Máxima suma de los segmentos

José A. Alonso,

Un segmento de una lista xs es una sublista de xs formada por elementos consecutivos en la lista. El problema de la máxima suma de segmentos consiste en dada una lista de números enteros calcular el máximo 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áxima 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ía.

Definir la función

   mss :: [Integer] -> Integer

tal que (mss xs) es la máxima suma de los segmentos de xs. Por ejemplo,

   mss [-1,2,-3,5,-2,1,3,-2,-2,-3,6]  ==  7
   mss [-1,-2,-3]                     ==  0
   mss [1..500]                       ==  125250
   mss [1..1000]                      ==  500500
   mss [-500..3]                      ==  6
   mss [-1000..3]                     ==  6

Soluciones

import Data.List (inits,tails)
 
-- 1ª solución
mss :: [Integer] -> Integer
mss = maximum . map sum . segmentos
 
-- (segmentos xs) es la lista de los segmentos de xs. Por ejemplo,
--    ghci> segmentos "abc"
--    ["","a","ab","abc","","b","bc","","c",""]
segmentos :: [a] -> [[a]]
segmentos = concat . map inits . tails
 
-- 2ª definición:
mss2 :: [Integer] -> Integer
mss2 = maximum . map (maximum . scanl (+) 0) . tails
 
-- 3ª definición:
mss3 :: [Integer] -> Integer
mss3 = maximum . map sum . concatMap tails . inits 
 
-- 4ª definición
mss4 :: [Integer] -> Integer
mss4  = fst . foldr (\x (b,a) -> (max (a+x) b, max 0 (a+x))) (0,0) 
 
-- 5ª definición (con scanl):
mss5 :: [Integer] -> Integer
mss5 = maximum . scanl (\a x -> max 0 a + x) 0
 
-- Comparación de eficiencia
-- =========================
 
--    ghci> mss [1..500]
--    125250
--    (7.52 secs, 2022130824 bytes)
--    
--    ghci> mss2 [1..500]
--    125250
--    (0.01 secs, 10474956 bytes)
--    
--    ghci> mss3 [1..500]
--    125250
--    (0.98 secs, 841862016 bytes)
--    
--    ghci> mss4 [1..500]
--    125250
--    (0.01 secs, 552252 bytes)
--    
--    ghci> mss2 [1..1000]
--    500500
--    (0.06 secs, 54575712 bytes)
--    
--    ghci> mss3 [1..1000]
--    500500
--    (7.87 secs, 7061347900 bytes)
--
--    ghci> mss4 [1..1000]
--    500500
--    (0.01 secs, 549700 bytes)
--    
--    ghci> mss2 [1..2000]
--    2001000
--    (0.29 secs, 216424336 bytes)
--    
--    ghci> mss2 [1..5000]
--    12502500
--    (2.37 secs, 1356384840 bytes)
--    
--    ghci> mss4 [1..5000]
--    12502500
--    (0.02 secs, 1913548 bytes)
--
--    ghci> mss5 [1..5000]
--    12502500
--    (0.01 secs, 2886360 bytes)

Pensamiento

Nubes, sol, prado verde y caserío
en la loma, revueltos. Primavera
puso en el aire de este campo frío
la gracia de sus chopos de ribera.

Antonio Machado

Medio
, , , , , , , , ,

5 soluciones de “Máxima suma de los segmentos”

  1. Responder
    frahidzam 
    mss :: [Integer] -> Integer
mss xs | esCreciente xs = sum (filter (> 0) xs)
       | esDecreciente xs = sum (filter (> 0) xs)
       | otherwise = aux xs (maximum xs) 2 
     where aux xs n a | a > length xs = n
                      | maximum (segmentos a xs) <= n = aux xs n (a+1)
                      | otherwise = aux xs (maximum (segmentos a xs)) (a+1)
           segmentos a xs | length xs < a = xs
                      | otherwise = (sum (take a xs)): segmentos a (drop 1 xs)
           esCreciente [] = True
           esCreciente [x] = True
           esCreciente (x:y:xs) | y >= x = esCreciente (y:xs)
                                | otherwise = False
           esDecreciente [] = True
           esDecreciente [x] = True
           esDecreciente (x:y:xs) | y <= x = esDecreciente (y:xs)
                                | otherwise = False
  2. Responder
    luipromor 
    mss :: [Integer] -> Integer
mss xs = aux xs 0 []
         where aux [] n ys | null ys = n
                           | otherwise = max n $ maximum ys
               aux (x:xs) n ys | n == 0 && x <0 = aux xs n  ys
                               | x<0 && n + x <=0 = aux xs 0 (n:ys)
                               | x <0 = aux xs (n+x) (n:ys)
                               | otherwise = aux xs (n+x) ys
  3. Responder
    adogargon 
    import Data.Matrix
 
mss :: [Integer] -> Integer
mss  = maximum . fmap sum. matriz
 
matriz :: [Integer] -> Matrix [Integer]
matriz xs = m
  where n = length xs
        m = matrix n n ((i,j) -> if i+j <= n+1 then (take j (drop (i-1) xs)) else [] )
  4. Responder
    alebarmor1 

    indexOf x xs = head [k | (n,k) <- zip xs [0..], x == n]
listaConsec [x] _ = True
listaConsec [] _ = True
listaConsec (x:y:xs) ys | (indexOf x ys) + 1 == indexOf y ys = listaConsec (y:xs) ys
                        | otherwise = False
powerSet [] = [[]]
powerSet (x:xs) = [x : cs | cs <- powerSet xs] ++ powerSet xs
filtroSegmentosConsec xss = [xs | xs <- (powerSet xss), listaConsec xs xss]
maximaSuma xs = maximum [sum xss | xss <- (filtroSegmentosConsec xs)]

  5. Responder
    javmarcha1 
    import Data.Matrix
 
mss :: [Integer] -> Integer
mss xs | all (>=0) xs = sum xs
       | all (<0) xs = 0
       | otherwise = maximum(toList(matrizSumaAPositivos xs)) 
 
matrizSumaAPositivos :: [Integer] -> Matrix Integer
matrizSumaAPositivos xs = m
 where m = matrix n n ((i,j) -> f i j)
       f i j | i > j = 0
             | i==j = fst (positivos xs !! (i-1))
             | otherwise = sum (drop (b i) (take (a j) xs))
       n = length (positivos xs)
       a y = snd(positivos xs !! (y-1))
       b z = snd(positivos xs !! (z-1))-1
       positivos xs = [(c,d)| (c,d) <- zip xs [1..], c>0]

Escribe tu solución

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.