Descripción del desafío

Una subsecuencia monotónica es una secuencia de números [a1, a2, ..., an]tal que

a1 <= a2 <= ... <= ano a1 >= a2 >= ... >= an. [1, 3, 3, 7, 9, 13, 13, 100]es una subsecuencia monotónica (no decreciente), así como [9, 4, 4, 3, 0, -10, -12](esta no aumenta), pero [1, 3, 6, 9, 8]no lo es. Dada una lista de enteros (en cualquier formato razonable), genera el número más pequeño de Nmodo que la secuencia de estos enteros se pueda dividir en Nsecuencias monotónicas.

Ejemplos

[1, 3, 7, 5, 4, 2] -> [[1, 3, 7], [5, 4, 2]] -> 2
[1, 2, 3, 4, 5, 6] -> [1, 2, 3, 4, 5, 6]     -> 1
[3, 1, 5, 5, 6]    -> [[3, 1], [5, 5, 6]]    -> 2
[4, 6, 8, 9, 1, 6] -> [[4, 6, 8, 9], [1, 6]] -> 2
[3, 3, 3, 3]       -> [[3, 3, 3, 3]]         -> 1
[7]                -> [[7]]                  -> 1
[]                 -> []                     -> anything (you don't actually have to handle an empty list case)
[1, 3, 2, -1, 6, 9, 10, 2, 1, -12] -> [[1, 3], [2, -1], [6, 9, 10], [2, 1, -12]] -> 4

Brachylog , 12 bytes

~c:{<=|>=}al

Pruébalo en línea!

Esto devuelve false.para la lista vacía [].

Explicación

(?)~c                 Take a list of sublists which when concatenated result in the Input
     :{<=|>=}a        Each sublist must be either increasing or decreasing
              l(.)    Output is the length of that list

Esto devolverá el más pequeño porque ~cgenerará puntos de elección desde el número más pequeño de sublistas hasta el más grande.

Perl, 65 bytes

62 bytes de código + 3 bytes para la -nbandera.

monot_seq.pl:

#!perl -n
s/\S+ /($_<=>$&)*($&<=>$')-$g>=0?$g=1:$.++;$g--;$_=$&/ge,$_=$.

Dé la entrada sin nueva línea final, con los números separados por espacios:

$ echo -n "1 3 2 -1 6 9 10 2 1 -12" | perl -M5.010 monot_seq.pl
4

-5 bytes gracias a @Gabriel Benamy.

Mathematica, 111 bytes

d=#[[2]]-#[[1]]&;r=Rest;f@{n_}:=1;f@k__:=If[d@k==0,f@r@k,g[k Sign@d@k]];g@{n_}:=1;g@k__:=If[d@k>0,g@r@k,1+f@r@k]

Función con nombre que ftoma una lista no vacía de números (enteros o incluso reales). Funciona de adelante hacia atrás, descarta el primer elemento repetidamente y realiza un seguimiento de cuántas subsecuencias se necesitan. Más detallado:

d = #[[2]] - #[[1]] &;         function: difference of the first two elements
r = Rest;                      function: a list with its first element dropped
f@{n_} := 1;                   f of a length-1 list equals 1
f@k__ := If[d@k == 0, f@r@k,   if the first two elements are equal, drop one
                                 element and call f again ...
            g[k Sign@d@k]];  ... otherwise call the helper function g on the
                                 list, multiplying by -1 if necessary to ensure
                                 that the list starts with an increase
g@{n_} := 1;                   g of a length-1 list equals 1
g@k__ := If[d@k > 0, g@r@k,    if the list starts with an increase, drop one
                                 element and call g again ...
            1 + f@r@k];        ... otherwise drop one element, call f on the
                                 resulting list, and add 1

Jalea , 19 bytes

IṠḟ0E
ŒṖÇ€€0e$Ðḟḅ1Ṃ

TryItOnline! o ejecutar todas las pruebas (la lista vacía da como resultado1)

¿Cómo?

IṠḟ0E - Link 1, test for monotonicity: a sublist
I     - incremental differences
 Ṡ    - sign {fall:-1; same:0; rise:1}
  ḟ0  - filter out the zeros
    E - all equal?

ŒṖÇ€€0e$Ðḟḅ1Ṃ - Main link
ŒṖ            - all partitions of the input list
  Ç€€         - call last link (1) as a monad for €ach for €ach
        Ðḟ    - filter out results:
       $      -    last two links as a monad
     0e       -        contains zero?
          ḅ1  - convert from unary (vectorises)
            Ṃ - minimum

(No estoy convencido de que este sea el método más adecuado para minimizar el recuento de bytes)

Perl, 98 97 96 79 bytes

($a,$b)=($a<=>$b)*($b<=>$c)<0?($c,shift,$d++):($b,$c)while$c=shift;say$d+1 if$a

La entrada se proporciona como una lista de números, separados por espacios, proporcionados en tiempo de ejecución, p. Ej.

perl -M5.010 monotonic.pl 1 3 2 -1 6 9 10 2 1 -12
4

(el 4 es la salida)

Legible:

($a,$b)=($a<=>$b)*($b<=>$c)<0
    ?($c,shift,$d++)
    :($b,$c)
  while$c=shift;
say$d+1
  if$a

El 'operador de nave espacial' <=>devuelve -1 si LHS <RHS, 0 si LHS = RHS y +1 si LHS> RHS. Al comparar los tres elementos secuenciales $a,$b,$cpara determinar si son monótona, sólo es necesario determinar que no es exactamente el caso de que uno de $a<=>$b, $b<=>$ces 1 y el otro es -1 - que sólo sucede cuando su producto es -1. Si bien $a==$bo $b==$c, entonces la secuencia es monotónica, y el producto es 0. Si $a < $b < $c, entonces ambos resultan en -1, y -1 * -1 = 1. Si $a > $b > $c, entonces ambos resultan en 1, y 1 * 1 = 1. En cualquier caso, la secuencia es monotónica y deseamos continuar.

Si el producto es menor que 0, sabemos que la secuencia no es monotónica, y descartamos los valores $a,$bque actualmente tenemos, e incrementamos nuestro contador de subsecuencia. De lo contrario, avanzamos un número.

No devuelve nada si la entrada está vacía; de lo contrario, devuelve el menor número de subsecuencias monotónicas contiguas.

C # 6, 297 209 bytes

using System.Linq;int G(int[] a)=>a.Any()?a.SkipWhile((x,i)=>i<1||x>=a[i-1]).Count()<a.SkipWhile((x,i)=>i<1||x<=a[i-1]).Count()?G(a.Select(x=>-x).ToArray()):G(a.SkipWhile((x,i)=>i<1||x<=a[i-1]).ToArray())+1:0;

Sin golfing con explicaciones

int G(int[] a)=>
    a.Any()
        ?a.SkipWhile((x,i)=>i<1||x>=a[i-1]).Count()<a.SkipWhile((x,i)=>i<1||x<=a[i-1]).Count()   // If a begins by decreasing (including whole a decreasing)...
            ?G(a.Select(x=>-x).ToArray())   // ... Then flip sign to make a begins by increasing
            :G(a.SkipWhile((x,i)=>i<1||x<=a[i-1]).ToArray())+1   // ... Else skip the increasing part, recursively find the remaining part number, then add 1
        :0;   // Return 0 if a is empty

JavaScript (ES6), 69 bytes

f=(d,c,b,...a)=>1/b?(d>c)*(b>c)+(d<c)*(b<c)?1+f(b,...a):f(d,b,...a):1

Toma la entrada como múltiples parámetros. Funciona comparando recursivamente los primeros tres elementos para ver si son monótonos, de ser así, elimina el elemento del medio ya que es inútil, si no, elimina los dos primeros elementos y comienza una nueva secuencia.

Clojure, 97 bytes

#((reduce(fn[[C i]s](let[S(conj C s)](if(or(apply <= S)(apply >= S))[S i][[s](inc i)])))[[]1]%)1)

reducerealiza un seguimiento de la subsecuencia actual y calcula cuántas veces <=y >=condiciones fallan. El último 1toma el segundo elemento del resultado (siendo el contador i).