Menu Close

Máxima suma de los segmentos

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

5 soluciones de “Máxima suma de los segmentos

  1. 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. 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. 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. 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. 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.