Máxima suma de elementos consecutivos

PorJosé A. Alonso 17-marzo-20161-mayo-2016

Definir la función

   sumaMaxima :: [Integer] -> Integer

1	sumaMaxima :: [Integer] -> Integer

tal que (sumaMaxima xs) es el valor máximo 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]      ==  500000500000

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] == 500000500000

Comprobar con QuickCheck que

   sumaMaxima xs == sumaMaxima (reverse xs)

1	sumaMaxima xs == sumaMaxima (reverse xs)

Soluciones

import Data.List (inits, tails)
import Test.QuickCheck

-- 1ª definición
-- =============

sumaMaxima1 :: [Integer] -> Integer
sumaMaxima1 [] = 0
sumaMaxima1 xs =
    maximum (0 : map sum [sublista xs i j | i <- [0..length xs - 1],
                                            j <- [i..length xs - 1]])

sublista :: [Integer] -> Int -> Int -> [Integer]
sublista xs i j =
    [xs!!k | k <- [i..j]]

-- 2ª definición
-- =============

sumaMaxima2 :: [Integer] -> Integer
sumaMaxima2 [] = 0
sumaMaxima2 xs = sumaMaximaAux 0 0 xs
    where m = maximum xs

sumaMaximaAux :: Integer -> Integer -> [Integer] -> Integer
sumaMaximaAux m v [] = max m v
sumaMaximaAux m v (x:xs)
    | x >= 0    = sumaMaximaAux m (v+x) xs
    | v+x > 0   = sumaMaximaAux (max m v) (v+x) xs
    | otherwise = sumaMaximaAux (max m v) 0 xs

-- 3ª definición
-- =============

sumaMaxima3 :: [Integer] -> Integer
sumaMaxima3 [] = 0
sumaMaxima3 xs = maximum (map sum (segmentos xs))

-- (segmentos xs) es la lista de los segmentos de xs. Por ejemplo 
--    segmentos "abc"  ==  ["", "a","ab","abc","b","bc","c"]
segmentos :: [a] -> [[a]]
segmentos xs =
    [] : concat [tail (inits ys) | ys <- init (tails xs)]

-- 4ª definición
-- =============

sumaMaxima4 :: [Integer] -> Integer
sumaMaxima4 [] = 0
sumaMaxima4 xs = 
    maximum (concat [scanl (+) 0 ys | ys <- tails xs])

-- Comprobación
-- ============

-- La propiedad es
prop_sumaMaxima :: [Integer] -> Bool
prop_sumaMaxima xs =
    sumaMaxima2 xs == n &&
    sumaMaxima3 xs == n &&
    sumaMaxima4 xs == n
    where n = sumaMaxima1 xs

-- La comprobación es
--    λ> quickCheck prop_sumaMaxima
--    +++ OK, passed 100 tests.

-- Comparación de eficiencia
-- =========================

--    λ> let n = 10^2 in sumaMaxima1 [-n..n] 
--    5050
--    (2.10 secs, 390,399,104 bytes)
--    λ> let n = 10^2 in sumaMaxima2 [-n..n] 
--    5050
--    (0.02 secs, 0 bytes)
--    λ> let n = 10^2 in sumaMaxima3 [-n..n] 
--    5050
--    (0.27 secs, 147,705,184 bytes)
--    λ> let n = 10^2 in sumaMaxima4 [-n..n] 
--    5050
--    (0.04 secs, 11,582,520 bytes)

prop_inversa :: [Integer] -> Bool
prop_inversa xs =
    sumaMaxima2 xs == sumaMaxima2 (reverse xs)

import Data.List (inits, tails)

import Test.QuickCheck

-- 1ª definición

-- =============

sumaMaxima1 :: [Integer] -> Integer

sumaMaxima1 [] = 0

sumaMaxima1 xs =

maximum (0 : map sum [sublista xs i j | i <- [0..length xs - 1],

j <- [i..length xs - 1]])

sublista :: [Integer] -> Int -> Int -> [Integer]

sublista xs i j =

[xs!!k | k <- [i..j]]

-- 2ª definición

-- =============

sumaMaxima2 :: [Integer] -> Integer

sumaMaxima2 [] = 0

sumaMaxima2 xs = sumaMaximaAux 0 0 xs

where m = maximum xs

sumaMaximaAux :: Integer -> Integer -> [Integer] -> Integer

sumaMaximaAux m v [] = max m v

sumaMaximaAux m v (x:xs)

| x >= 0 = sumaMaximaAux m (v+x) xs

| v+x > 0 = sumaMaximaAux (max m v) (v+x) xs

| otherwise = sumaMaximaAux (max m v) 0 xs

-- 3ª definición

-- =============

sumaMaxima3 :: [Integer] -> Integer

sumaMaxima3 [] = 0

sumaMaxima3 xs = maximum (map sum (segmentos xs))

-- (segmentos xs) es la lista de los segmentos de xs. Por ejemplo

-- segmentos "abc" == ["", "a","ab","abc","b","bc","c"]

segmentos :: [a] -> [[a]]

segmentos xs =

[] : concat [tail (inits ys) | ys <- init (tails xs)]

-- 4ª definición

-- =============

sumaMaxima4 :: [Integer] -> Integer

sumaMaxima4 [] = 0

sumaMaxima4 xs =

maximum (concat [scanl (+) 0 ys | ys <- tails xs])

-- Comprobación

-- ============

-- La propiedad es

prop_sumaMaxima :: [Integer] -> Bool

prop_sumaMaxima xs =

sumaMaxima2 xs == n &&

sumaMaxima3 xs == n &&

sumaMaxima4 xs == n

where n = sumaMaxima1 xs

-- La comprobación es

-- λ> quickCheck prop_sumaMaxima

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

-- =========================

-- λ> let n = 10^2 in sumaMaxima1 [-n..n]

-- 5050

-- (2.10 secs, 390,399,104 bytes)

-- λ> let n = 10^2 in sumaMaxima2 [-n..n]

-- 5050

-- (0.02 secs, 0 bytes)

-- λ> let n = 10^2 in sumaMaxima3 [-n..n]

-- 5050

-- (0.27 secs, 147,705,184 bytes)

-- λ> let n = 10^2 in sumaMaxima4 [-n..n]

-- 5050

-- (0.04 secs, 11,582,520 bytes)

prop_inversa :: [Integer] -> Bool

prop_inversa xs =

sumaMaxima2 xs == sumaMaxima2 (reverse xs)

9 Comentarios

-- Poco eficiente

sumaMaxima :: [Integer] -> Integer
sumaMaxima [] = 0
sumaMaxima xs = maximum (map (sum) (valoresConsecutivos xs))

valoresConsecutivos :: Eq t => [t] -> [[t]]
valoresConsecutivos [] = [[]]
valoresConsecutivos xs = [ zs | zs <- (valoresM xs), isInfixOf zs xs]

valoresM :: Eq t => [t] -> [[t]]
valoresM [] = [[]]
valoresM (x:xs) = nub (subsequences (x:xs) ++ (valoresM (xs)))

-- Poco eficiente

sumaMaxima :: [Integer] -> Integer

sumaMaxima [] = 0

sumaMaxima xs = maximum (map (sum) (valoresConsecutivos xs))

valoresConsecutivos :: Eq t => [t] -> [[t]]

valoresConsecutivos [] = [[]]

valoresConsecutivos xs = [ zs | zs <- (valoresM xs), isInfixOf zs xs]

valoresM :: Eq t => [t] -> [[t]]

valoresM [] = [[]]

valoresM (x:xs) = nub (subsequences (x:xs) ++ (valoresM (xs)))

Responder

prop_sumaMaxima :: [Integer] -> Bool
prop_sumaMaxima xs = sumaMaxima xs == sumaMaxima (reverse xs)

-- *Main> quickCheckWith (stdArgs {maxSize=10}) prop_sumaMaxima
-- +++ OK, passed 100 tests.

prop_sumaMaxima :: [Integer] -> Bool

prop_sumaMaxima xs = sumaMaxima xs == sumaMaxima (reverse xs)

-- *Main> quickCheckWith (stdArgs {maxSize=10}) prop_sumaMaxima

-- +++ OK, passed 100 tests.

Responder

import Data.List
import Test.QuickCheck

sumaMaxima :: [Integer] -> Integer
sumaMaxima xs = maximum[sum zs|zs<- (consecutivos xs)]

consecutivos ::[Integer]->[[Integer]]
consecutivos xs = [ys|ys<-subsequences xs,ys`isInfixOf` xs]

prop_sumaMaxima :: [Integer]->Bool
prop_sumaMaxima xs = sumaMaxima xs == sumaMaxima(reverse xs)

-- quickCheckWith (stdArgs {maxSize=7}) prop_sumaMaxima
-- +++ OK, passed 100 tests.

import Data.List

import Test.QuickCheck

sumaMaxima :: [Integer] -> Integer

sumaMaxima xs = maximum[sum zs|zs<- (consecutivos xs)]

consecutivos ::[Integer]->[[Integer]]

consecutivos xs = [ys|ys<-subsequences xs,ys`isInfixOf` xs]

prop_sumaMaxima :: [Integer]->Bool

prop_sumaMaxima xs = sumaMaxima xs == sumaMaxima(reverse xs)

-- quickCheckWith (stdArgs {maxSize=7}) prop_sumaMaxima

-- +++ OK, passed 100 tests.

Responder

import Data.List
import Test.QuickCheck

sumaMaxima :: [Integer] -> Integer
sumaMaxima xs = if all (>0) xs then sum xs else if all (<0) xs then 0
                                                else maximaSuma xs

maximaSuma :: (Num a, Ord a) => [a] -> a
maximaSuma xs = maximum [sum ys| ys <- irQuitandoDelante xs ++
                                       irQuitandoDetras xs ++ quitaDyD xs]

irQuitandoDelante :: [a] -> [[a]]
irQuitandoDelante  xs = [drop x xs | x <- [0..length xs -1]]

irQuitandoDetras :: [a] -> [[a]]
irQuitandoDetras xs = [take x xs | x <- [0..length xs -1]]

quitaDyD:: [a] -> [[a]]
quitaDyD xs = 
  [drop x (take y xs) | x <- [0..length xs -1], y <- [length xs-1,length xs-2..0],
              not (null(drop x (take y xs)))]


prop :: [Integer] -> Bool
prop xs = sumaMaxima xs == sumaMaxima (reverse xs)

-- λ> quickCheck prop
-- +++ OK, passed 100 tests.

import Data.List

import Test.QuickCheck

sumaMaxima :: [Integer] -> Integer

sumaMaxima xs = if all (>0) xs then sum xs else if all (<0) xs then 0

else maximaSuma xs

maximaSuma :: (Num a, Ord a) => [a] -> a

maximaSuma xs = maximum [sum ys| ys <- irQuitandoDelante xs ++

irQuitandoDetras xs ++ quitaDyD xs]

irQuitandoDelante :: [a] -> [[a]]

irQuitandoDelante xs = [drop x xs | x <- [0..length xs -1]]

irQuitandoDetras :: [a] -> [[a]]

irQuitandoDetras xs = [take x xs | x <- [0..length xs -1]]

quitaDyD:: [a] -> [[a]]

quitaDyD xs =

[drop x (take y xs) | x <- [0..length xs -1], y <- [length xs-1,length xs-2..0],

not (null(drop x (take y xs)))]

prop :: [Integer] -> Bool

prop xs = sumaMaxima xs == sumaMaxima (reverse xs)

-- λ> quickCheck prop

-- +++ OK, passed 100 tests.

Responder

sumaMaxima :: [Integer] -> Integer
sumaMaxima [] = 0
sumaMaxima xs | signum d == -1 = 0
              | otherwise = d
              where d = maximum $ scanl1 (+) xs

sumaMaxima :: [Integer] -> Integer

sumaMaxima [] = 0

sumaMaxima xs | signum d == -1 = 0

| otherwise = d

where d = maximum $ scanl1 (+) xs

Responder

Chema Cortés dice:

18-marzo-2016 a las 15:56

Falla con sumaMaxima [-1, -2, -3, 100]

Responder

fracruzam dice:

17-marzo-2016 a las 16:08

Versión en Maxima, con un bucle «for»

Haskell

sumaMaxima (xs) := block([s:0,p:0], for x in xs do ( p : p + x, s : max(p,s)), s)$

1
2
3
4
5

sumaMaxima (xs) := block([s:0,p:0],
  for x in xs do (
    p : p + x,
    s : max(p,s)),
  s)$

Responder

import Data.List
import Test.QuickCheck
 
sumaMaxima :: [Integer] -> Integer
sumaMaxima xs = if all (>=0) xs then sum xs else if all (<0) xs then 0
                                                else maximaSuma xs
 
maximaSuma :: (Num a, Ord a) => [a] -> a
maximaSuma xs = maximum [sum ys| ys <- irQuitandoDelante xs ++
                                       irQuitandoDetras xs ++ quitaDyD xs]
 
irQuitandoDelante :: [a] -> [[a]]
irQuitandoDelante  xs = [drop x xs | x <- [0..length xs -1]]
 
irQuitandoDetras :: [a] -> [[a]]
irQuitandoDetras xs = [take x xs | x <- [0..length xs -1]]
 
quitaDyD:: [a] -> [[a]]
quitaDyD xs = 
  [drop x (take y xs) | x <- [0..length xs -1], y <- [length xs-1,length xs-2..0],
              not (null(drop x (take y xs)))]
 
 
prop :: [Integer] -> Bool
prop xs = sumaMaxima xs == sumaMaxima (reverse xs)
 
-- λ> quickCheck prop
-- +++ OK, passed 100 tests.

import Data.List

import Test.QuickCheck

sumaMaxima :: [Integer] -> Integer

sumaMaxima xs = if all (>=0) xs then sum xs else if all (<0) xs then 0

else maximaSuma xs

maximaSuma :: (Num a, Ord a) => [a] -> a

maximaSuma xs = maximum [sum ys| ys <- irQuitandoDelante xs ++

irQuitandoDetras xs ++ quitaDyD xs]

irQuitandoDelante :: [a] -> [[a]]

irQuitandoDelante xs = [drop x xs | x <- [0..length xs -1]]

irQuitandoDetras :: [a] -> [[a]]

irQuitandoDetras xs = [take x xs | x <- [0..length xs -1]]

quitaDyD:: [a] -> [[a]]

quitaDyD xs =

[drop x (take y xs) | x <- [0..length xs -1], y <- [length xs-1,length xs-2..0],

not (null(drop x (take y xs)))]

prop :: [Integer] -> Bool

prop xs = sumaMaxima xs == sumaMaxima (reverse xs)

-- λ> quickCheck prop

-- +++ OK, passed 100 tests.

Responder

import Data.List
import Test.QuickCheck

sumaMaxima :: [Integer] -> Integer
sumaMaxima = aux 0
    where aux m [] = m
          aux m (x:xs) | m+x < 0   = m `max` aux 0 xs
                       | otherwise = m `max` aux (m+x) xs

prop_sumaMaxima :: [Integer] -> Bool
prop_sumaMaxima xs = 
    sumaMaxima xs == sumaMaxima (reverse xs)

import Data.List

import Test.QuickCheck

sumaMaxima :: [Integer] -> Integer

sumaMaxima = aux 0

where aux m [] = m

aux m (x:xs) | m+x < 0 = m `max` aux 0 xs

| otherwise = m `max` aux (m+x) xs

prop_sumaMaxima :: [Integer] -> Bool

prop_sumaMaxima xs =

sumaMaxima xs == sumaMaxima (reverse xs)

Responder

Máxima suma de elementos consecutivos

Soluciones

9 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Se puede imprimir o compartir con

9 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico