Máxima longitud de sublistas crecientes

4 Comentarios

1. Haskell

   longitudMayorSublistaCreciente :: Ord a => [a] -> Int longitudMayorSublistaCreciente xs = longitudSCM xs (sort (nub xs)) longitudSCM :: Eq a => [a] -> [a] -> Int longitudSCM xs ys = (matrizLongitudSCM xs ys) ! (n,m) where n = length xs m = length ys matrizLongitudSCM :: Eq a => [a] -> [a] -> Array (Int,Int) Int matrizLongitudSCM xs ys = q where n = length xs m = length ys v = listArray (1,n) xs w = listArray (1,m) ys q = array ((0,0),(n,m)) [((i,j), f i j) | i <- [0..n], j <- [0..m]] where f 0 _ = 0 f _ 0 = 0 f i j | v ! i == w ! j = 1 + q ! (i-1,j-1) | otherwise = max (q ! (i-1,j)) (q ! (i,j-1))

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

   longitudMayorSublistaCreciente :: Ord a => [a] -> Int longitudMayorSublistaCreciente xs =   longitudSCM xs (sort (nub xs))   longitudSCM :: Eq a => [a] -> [a] -> Int longitudSCM xs ys = (matrizLongitudSCM xs ys) ! (n,m)   where n = length xs         m = length ys   matrizLongitudSCM :: Eq a => [a] -> [a] -> Array (Int,Int) Int matrizLongitudSCM xs ys = q   where     n = length xs     m = length ys     v = listArray (1,n) xs     w = listArray (1,m) ys     q = array ((0,0),(n,m)) [((i,j), f i j) | i <- [0..n], j <- [0..m]]       where f 0 _ = 0             f _ 0 = 0             f i j | v ! i == w ! j = 1 + q ! (i-1,j-1)                   | otherwise      = max (q ! (i-1,j)) (q ! (i,j-1))

   Responder

2. Haskell

   longitudMayorSublistaCreciente :: Ord a => [a] -> Int longitudMayorSublistaCreciente xs = maximum [ f (longitudIntervalos (drop n xs) (head (drop n xs))) n | n <- [0..length xs-1]] where longitudIntervalos [] _ = 0 longitudIntervalos [x] y | y < x = 1 | otherwise = 0 longitudIntervalos (x:xs) y | x <= y = longitudIntervalos xs y | longitudIntervalos xs y > longitudIntervalos xs x =longitudIntervalos xs y | otherwise = longitudIntervalos xs x + 1 f y n | head (drop n xs) < head xs = y | otherwise = 1 + y

   1 2 3 4 5 6 7 8 9 10 11 12

   longitudMayorSublistaCreciente :: Ord a => [a] -> Int longitudMayorSublistaCreciente xs =  maximum [ f (longitudIntervalos (drop n xs)  (head (drop n xs))) n | n <- [0..length xs-1]]   where longitudIntervalos [] _ =  0         longitudIntervalos [x] y | y < x = 1                                  | otherwise = 0         longitudIntervalos (x:xs) y | x <= y = longitudIntervalos xs y                                     | longitudIntervalos xs y > longitudIntervalos xs x  =longitudIntervalos xs y                                                                            | otherwise = longitudIntervalos xs x + 1                                                f y n  | head (drop n xs) <  head xs = y              | otherwise = 1 + y

   Responder

3. Haskell

   import Data.List import Data.Array -- 1º SOLUCIÓN : (NO CALCULA EL ÚLTIMO CASO EN MENOS DE 3s) longitudMayorSublistaCreciente :: Ord a => [a] -> Int longitudMayorSublistaCreciente xs | esCreciente xs = length xs | esDecreciente xs = 1 | otherwise = maximum (map (length) (todas xs)) posicion :: Ord a => a -> [a] -> Int posicion x (y:xs) | x==y = 1 | otherwise = 1 + posicion x xs mayores :: Ord a => a -> [a] -> [[a]] mayores x xs = [[y] | y <- xs , y > x, posicion y xs > posicion x xs] unirAux :: [a] -> [[a]] -> [[a]] unirAux xs xss = [xs++ys | ys <- xss] unir :: Eq a => [[a]] -> [[a]] -> [[a]] unir xss [] = xss unir xss yss = concat[unirAux xs yss | xs <- xss] listas :: Ord a => [[a]] -> [a] -> [[a]] listas xss xs = concat[unir [xss !! a] (mayores x (dropWhile (/=x) xs)) | (x,a) <- zip (map (last) xss) [0..]] recursion :: Ord a => [[a]] -> [a] -> [[a]] -> [[a]] recursion xss xs yss | listas xss xs == yss = yss | otherwise = recursion (listas xss xs) xs (listas xss xs) inicios :: Ord a => [a] -> [[[a]]] inicios xs = [ [[x]] | x <- xs] todas :: Ord a => [a] -> [[a]] todas xs = concat[recursion xss xs xss | xss <- (inicios xs)] esCreciente :: Ord a => [a] -> Bool esCreciente xs = and[ y>x | (x,y) <- zip xs (tail xs)] esDecreciente :: Ord a => [a] -> Bool esDecreciente xs = and[ y<x | (x,y) <- zip xs (tail xs)] -- 2º SOLUCIÓN longitudMayorSublistaCreciente2 :: Ord a => [a] -> Int longitudMayorSublistaCreciente2 xs = longitudSCM xs (sort (nub xs)) longitudSCM :: Eq a => [a] -> [a] -> Int longitudSCM xs ys = (matrizLongitudSCM xs ys) ! (n,m) where n = length xs m = length ys matrizLongitudSCM :: Eq a => [a] -> [a] -> Array (Int,Int) Int matrizLongitudSCM xs ys = q where n = length xs m = length ys v = listArray (1,n) xs w = listArray (1,m) ys q = array ((0,0),(n,m)) [((i,j), f i j) | i <- [0..n], j <- [0..m]] where f 0 _ = 0 f _ 0 = 0 f i j | v ! i == w ! j = 1 + q ! (i-1,j-1) | otherwise = max (q ! (i-1,j)) (q ! (i,j-1))

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66

   import Data.List import Data.Array   -- 1º SOLUCIÓN : (NO CALCULA EL ÚLTIMO CASO EN MENOS DE 3s) longitudMayorSublistaCreciente :: Ord a => [a] -> Int longitudMayorSublistaCreciente xs | esCreciente xs  = length xs                                   | esDecreciente xs = 1                                   | otherwise = maximum (map (length) (todas xs))    posicion :: Ord a => a -> [a] -> Int posicion x (y:xs) | x==y = 1                   | otherwise = 1 + posicion x xs   mayores :: Ord a => a -> [a] -> [[a]] mayores x xs = [[y] | y <- xs , y > x,                 posicion y xs > posicion x xs]   unirAux :: [a] -> [[a]] -> [[a]] unirAux xs xss = [xs++ys | ys <- xss]   unir :: Eq a => [[a]] -> [[a]] -> [[a]] unir xss [] = xss unir xss yss = concat[unirAux xs yss | xs <- xss]   listas :: Ord a => [[a]] -> [a] -> [[a]] listas xss xs = concat[unir [xss !! a] (mayores x (dropWhile (/=x) xs)) |                        (x,a) <- zip (map (last) xss) [0..]] recursion :: Ord a => [[a]] -> [a] -> [[a]] -> [[a]] recursion xss xs yss | listas xss xs == yss = yss                      | otherwise = recursion (listas xss xs) xs (listas xss xs)   inicios :: Ord a => [a] -> [[[a]]] inicios xs = [ [[x]] | x <- xs]   todas :: Ord a => [a] -> [[a]] todas xs = concat[recursion xss xs xss | xss <- (inicios xs)]   esCreciente :: Ord a => [a] -> Bool esCreciente xs = and[ y>x | (x,y) <- zip xs (tail xs)]   esDecreciente :: Ord a => [a] -> Bool esDecreciente xs = and[ y<x | (x,y) <- zip xs (tail xs)]   -- 2º SOLUCIÓN   longitudMayorSublistaCreciente2 :: Ord a => [a] -> Int longitudMayorSublistaCreciente2 xs =   longitudSCM xs (sort (nub xs)) longitudSCM :: Eq a => [a] -> [a] -> Int longitudSCM xs ys = (matrizLongitudSCM xs ys) ! (n,m)   where n = length xs         m = length ys matrizLongitudSCM :: Eq a => [a] -> [a] -> Array (Int,Int) Int matrizLongitudSCM xs ys = q   where     n = length xs     m = length ys     v = listArray (1,n) xs     w = listArray (1,m) ys     q = array ((0,0),(n,m)) [((i,j), f i j) | i <- [0..n], j <- [0..m]]       where f 0 _ = 0             f _ 0 = 0             f i j | v ! i == w ! j = 1 + q ! (i-1,j-1)                   | otherwise      = max (q ! (i-1,j)) (q ! (i,j-1))

   Responder

4. Solución en Maxima:

   sublistasCrecientes (xs):=
   if emptyp (xs) then [[]] 
   else g(xs) $
   g(xs):=  append (sublistasCrecientes (tail(xs)),
   makelist(f(head (xs),ys), ys,sublistasCrecientes (rest(xs,1))))$
   f(x,ys) :=if emptyp(ys) then cons(x,ys) else if x<first(ys)
   then cons(x,ys) else []$
   correccion (xs):=unique(delete([],sublistasCrecientes (xs)))$
   longitudMaximaSublistasCrecientes (xs):=lmax (map (length,correccion(xs)))$

   Responder