Introdução

Suponha que você queira calcular os máximos finais de uma lista de números, ou seja, o máximo de cada sufixo não vazio. Uma maneira de fazer isso é escolher repetidamente um número e substituí-lo por um número maior ocorrendo depois dele, até que isso não seja mais possível. Nesse desafio, sua tarefa é executar uma etapa deste algoritmo.

A tarefa

Sua entrada é uma lista de números inteiros L , que podem estar vazios. Sua saída será a lista L, onde exatamente um número L _i foi substituído por outro L _j , onde L _i <L _j e i <j .

Em outras palavras, você deve substituir um número por um número maior que ocorra após ele.

Você pode escolher i e j livremente entre todos os pares válidos, ea escolha pode ser não-determinístico.

Se tal i e j não existem (ou seja, L é não aumentar), sua saída será L inalterado.

Exemplo

Considere a entrada L = [3, 1, 4, -1, 2] . As operações possíveis são substituir 3 por 4 , substituir 1 por 4 , substituir 1 por 2 ou substituir -1 por 2 . Assim, as saídas possíveis são:

 [  3 ,   1 ,   4 ,  -1 ,   2 ]
 ------------------------------
 [( 4),   1 ,(  4),  -1 ,   2 ]
 [  3 ,(  4),(  4),  -1 ,   2 ]
 [  3 ,(  2),   4 ,  -1 ,(  2)]
 [  3 ,   1 ,   4 ,(  2),(  2)]

Se você repetir as vezes suficientes operação, o resultado final será [4,4,4,2,2] , que é precisamente a lista de maxima cauda de L .

Regras e pontuação

Você pode escrever um programa completo ou uma função. No último caso, você pode modificar a entrada no lugar em vez de retornar uma nova matriz, se o seu idioma permitir. Os formatos de entrada e saída são flexíveis dentro do motivo.

A menor contagem de bytes vence.

Casos de teste

Todas as saídas possíveis são mostradas.

[] -> []
[1] -> [1]
[1,2] -> [2,2]
[2,1] -> [2,1]
[4,4,4,4] -> [4,4,4,4]
[-1,-3,-10] -> [-1,-3,-10]
[1,3,10] -> [3,3,10] [10,3,10] [1,10,10]
[1,1,2,1] -> [2,1,2,1] [1,2,2,1]
[998,64,2,-94,-789] -> [998,64,2,-94,-789]
[998,2,64,-94,-789] -> [998,64,64,-94,-789]
[3,1,4,-1,2] -> [4,1,4,-1,2] [3,4,4,-1,2] [3,2,4,-1,2] [3,1,4,2,2]
[-1,4,0,4,7,2,3] -> [4,4,0,4,7,2,3] [0,4,0,4,7,2,3] [-1,4,4,4,7,2,3] [7,4,0,4,7,2,3] [-1,7,0,4,7,2,3] [-1,4,7,4,7,2,3] [-1,4,0,7,7,2,3] [2,4,0,4,7,2,3] [-1,4,2,4,7,2,3] [3,4,0,4,7,2,3] [-1,4,3,4,7,2,3] [-1,4,0,4,7,3,3]
[3542,-12311,7662,1672,6081] -> [7662,-12311,7662,1672,6081] [3542,7662,7662,1672,6081] [3542,1672,7662,1672,6081] [6081,-12311,7662,1672,6081] [3542,6081,7662,1672,6081] [3542,-12311,7662,6081,6081]

JavaScript (ES6), 41 40 39 38 bytes

Guardou um byte graças a @Neil, outro obrigado a @ user81655

x=>x.map(c=>c<x[++i]>d?x[d=i]:c,d=i=0)

Apenas quando parece reduceRightque finalmente pode ter uma chance, .mapaparece mais uma vez ...

Mathematica, 37 bytes

#/.{a___,b_,c_,d___}/;b<c:>{a,c,c,d}&

Função pura obtendo uma lista de números reais pares e retornando uma lista de números reais. Procura o primeiro par de entradas consecutivas na ordem "errada" e substitui o primeiro desse par pelo segundo. Um bom comportamento padrão /.significa que ele retorna a entrada inalterada quando apropriado.

Nota lateral divertida: se substituirmos b<cpor !OrderedQ[{c,b}], então a função funcionará em strings (e realmente em qualquer tipo de dados depois que a ordem apropriada for descrita). Por exemplo, #/.{a___,b_,c_,d___}/;!OrderedQ[{c,b}]:>{a,c,c,d}&nos {"programming", "puzzles", "code", "golf"}retornos de entrada {"puzzles", "puzzles", "code", "golf"}.

JavaScript (ES6), 43 39 38 bytes

a=>a[a.some(e=>e<a[++i],i=0)*i-1]=a[i]

Saídas modificando a matriz no local. Editar: salvou 4 bytes graças a @ETHproductions. Guardou 1 byte graças a @ user81655.

Haskell , 36 bytes

f(a:r@(b:_))|a<b=b:r|1>0=a:f r
f e=e

Experimente online!

Procure na lista elementos consecutivos a,bcom a<be altere-os para b,b.

Aprimorado de 37 bytes:

f(a:b:t)|a<b=b:b:t
f(a:t)=a:f t
f e=e

Geléia , 13 11 bytes

ṫJṀ€ż¹ŒpQ-ị

Substitui o mais à direita de todos os números possíveis.

Experimente online!

Como funciona

ṫJṀ€ż¹ŒpQ-ị  Main link. Argument: A (array)

 J           Yield all indices of A, i.e., the array [1, ..., len(A)].
ṫ            Dyadic tail; for index k, take all elements starting with the k-th.
             This constructs the array of suffixes.
  Ṁ€         Maximum each; map the monadic maximum atom over the suffixes.
     ¹       Identity; yield A.
    ż        Zip; construct all pairs of elements of the result to the left and the
             corresponding elements of the result to the right.
      Œp     Cartesian product. Construct all arrays that, for each index, take
             either the left or the right element.
        Q    Unique; deduplicate the resulting arrays.
         -ị  At-index -1; select the second to last result.
             The last result is A itself, the first maxima of suffixes.

MATL , 15 bytes

tdt0>0whY>d*0h+

Experimente online!

Eu não sou um grande fã desta solução. Parece terrivelmente ineficiente para mim. Particularmente as seções whY>d*e 0h+.

Python 2, 139 134 93 bytes

a=input()
for i in range(len(a)):
 for j in a[i+1:]:
    if a[i]<j:a[i]=j;print a;exit()
print a

Terrivelmente longo, mas é uma primeira tentativa.

-5 bytes graças ao TemporalWolf
-41 (!!) bytes graças ao Value Ink

MATL , 13 bytes

ttd0>fX>Q)2M(

Experimente online!

Explicação

As duas condições a seguir são equivalentes:

1. Há um número que tem um número maior à sua direita
2. Há um número que tem um número maior imediatamente à sua direita

O código usa a condição 2, que é mais simples. Ele calcula incrementos consecutivos e encontra o último positivo, se houver. Para as duas entradas envolvidas, ele grava o valor da segunda entrada na primeira.

Esse truque é usado para lidar com o caso quando nenhuma substituição pode ser feita. Observe também que a indexação do MATL é 1baseada.

Vamos usar a entrada [3,1,4,-1,2]como um exemplo.

tt    % Get input implicitly and duplicate it twice
      % STACK: [3,1,4,-1,2], [3,1,4,-1,2], [3,1,4,-1,2]
d     % Consecutive differences
      % STACK: [3,1,4,-1,2], [3,1,4,-1,2], [-2  3 -5  3]
0>    % Are they positive?
      % STACK: [3,1,4,-1,2], [3,1,4,-1,2], [0 1 0 1]
f     % Find indices of all positive differences. Result may be empty
      % STACK: [3,1,4,-1,2], [3,1,4,-1,2], [2 4]
X>    % Maximum index with a positive difference. Empty input remains as empty
      % STACK: [3,1,4,-1,2], [3,1,4,-1,2], 4
Q     % Add 1. Since the addition is elementwise, empty input remains as empty
      % STACK: [3,1,4,-1,2], [3,1,4,-1,2], 5
)     % Get the entry of the input at that position
      % STACK: [3,1,4,-1,2], 2
2M    % Push maximum index with a positive difference, again
      % STACK: [3,1,4,-1,2], 2, 4
(     % Assign to that position. Implicitly display
      % STACK: [3,1,4,2,2]

Haskell , 34 33 bytes

Isso é baseado na resposta de xnor , que sugeriu que eu a publicasse.

EDIT: xnor encontrou um byte para salvar.

f(a:r@(b:_))=max(b:r)$a:f r
f e=e

Experimente online!

Basicamente, observei que a ramificação do método xnor sempre acaba escolhendo a expressão que for maior, já que Haskell usa ordenação lexicográfica para listas. (O caso a==btambém funciona porque f r>=r, o que pode ser provado separadamente por indução.)

Dito de forma diferente, sempre que b:r > a:f r, então, b:ré uma resposta correta, e do contrário podemos recorrer a:f r.

Então, em vez de verificar a<bcom antecedência, apenas calculo as duas expressões e tomo o máximo. Isso pode causar uma explosão exponencial, embora a preguiça de Haskell evite isso, a menos que seja ae bseja igual.

Python 3, 79 bytes

def f(x):
 for i,a in enumerate(x):
  m=max(x[i+1:])
  if m>a:x[i]=m;break

Muda a matriz original (lista) fornecida a ela. Estou infeliz por não ser um lambda e tenho certeza de que há melhores otimizações; Espero que eu resolva isso mais tarde.

Breve explicação

Leva o máximo da matriz além do elemento atual (começando com o zeroth). Ele então compara isso ao próprio elemento: se o máximo for maior, substitua o elemento atual por ele e pare, caso contrário, aumente por um e continue tentando.

Ruby, 66 61 bytes

->a{i=r=-1;a.map{|e|m=a[i+=1,a.size].max;r&&m>e ?(r=!r;m):e}}

Experimente online!

C, 47 bytes

f(p,n)int*p;{n>1?*p<p[1]?*p=p[1]:f(p+1,n-1):0;}

Implementação recursiva, tendo como entrada um ponteiro para o primeiro elemento de uma matriz e o comprimento da matriz. Modifica a matriz no local.

SWI-Prolog, 70 bytes

f([H|T],[S|T]):-max_list(T,S),S>H,!.
f([H|T],[H|R]):-f(T,R),!.
f(I,I).

A primeira cláusula substitui o primeiro elemento da lista pelo valor máximo do restante da lista, mas apenas se esse máximo for maior. A segunda cláusula chama recursivamente o predicado para o final da lista. Se nenhuma dessas cláusulas tiver êxito, a terceira cláusula simplesmente retorna a entrada.

Este retorno é apenas uma das soluções possíveis. É trivial encontrar todos eles com código muito semelhante, mas o caso em que nenhuma alteração é possível leva muito mais bytes para ser tratado.

Exemplo:

?- f([-1,4,0,4,7,2,3], O).
O = [7, 4, 0, 4, 7, 2, 3]

R, 71 bytes

a=scan()
l=length(a) 
lapply(1:l,function(x){
  a[x]=max(a[x:l])
  a
})

C, 80 bytes

i,j;f(l,n)int*l;{for(i=0;i<n;++i)for(j=i;++j<n;)if(l[i]<l[j]){l[i]=l[j];j=i=n;}}

Ligue para:

int main()
{
    int a[5]={3,1,4,-1,2};
    f(a,5);
    for(int k=0;k<5;++k)
        printf("%d ", a[k]);
}

Python 2, 89 bytes

Experimente online -1 byte graças a @TemporalWolf
-25 bytes graças a @ValueInk
-7 bytes graças a @Cole

Função que muda a matriz de entrada

def F(A):
 for i in range(len(A)):
    r=[y for y in A[i+1:]if y>A[i]]
    if r:A[i]=r[0];break

Se não houvesse necessidade de parar após a primeira iteração, seria um pouco mais bonito

Python 2, 60 bytes

f=lambda x:x and[x[:1]+f(x[1:]),[max(x)]+x[1:]][x[0]<max(x)]

Experimente Online!

Explicação: Verifica recursivamente se um determinado elemento é menor que o maxelemento no restante da lista. Nesse caso, retorna a lista maxsubstituindo o primeiro elemento.

TI-Básico, 72 bytes

Prompt L1
If 2≤dim(L1
Then
For(A,1,dim(L1)-1
For(B,A,dim(L1
If L1(A)<L1(B
Then
L1(B→L1(A
Goto E
End
End
End
End
Lbl E
L1

Explicação:

Prompt L1          # 4 bytes, input list
If 2≤dim(L1        # 7 bytes, if the list has 2 or 1 element(s), skip this part and return it
Then               # 2 bytes
For(A,1,dim(L1)-1  # 12 bytes, for each element in the list other than the last
For(B,A,dim(L1     # 9 bytes, for each element after that one
If L1(A)<L1(B      # 12 bytes, if the second is larger than the first
Then               # 2 bytes
L1(B→L1(A          # 10 bytes, replace the first with the second
Goto E             # 3 bytes, and exit
End                # 2 bytes
End                # 2 bytes
End                # 2 bytes
End                # 2 bytes
Lbl E              # 3 bytes
L1                 # 2 bytes, implicitly return L1

sh, 118 bytes

Inteiros de entrada são passados ​​como argumentos para o script.

l=("$@");for i in "$@";{ for j in "$@";{(($i<$j))&&{ l[$x]=$j;echo ${l[@]};exit;};};shift;x=`expr $x+1`;};echo ${l[@]}

Demolir:

l=("$@");                      #copy original list
for i in "$@";{ for j in "$@"; #check all elements j that follow element i in list
{(($i<$j))&&{ l[$x]=$j;echo ${l[@]};exit;};};   #if i<j, make i=j; print list, done
shift;                         #makes sure that i is compared only to j that occur after it
x=`expr $x+1`;};               #keeps track of i'th position in the list
echo ${l[@]}                   #prints list if it was unchanged

PHP, 88 bytes

<?for(;$i+1<$c=count($a=$_GET)&&$a[+$i]>=$a[++$i];);$i>=$c?:$a[$i-1]=$a[$i];print_r($a);

Demolir

for(;
$i+1<($c=count($a=$_GET))  # first condition end loop if the item before the last is reach 
&&$a[+$i]>=$a[++$i] # second condition end loop if item is greater then before 
;);
$i>=$c?:$a[$i-1]=$a[$i]; # replace if a greater item is found
print_r($a); #Output

Haskell, 48 bytes

f(b:l)|l>[],m<-maximum l,b<m=m:l|1<2=b:f l
f x=x

Exemplo de uso: f [1,1,2,1]-> [2,1,2,1]. Experimente online! .

Se a lista de entrada tiver pelo menos um elemento, vincule b- se ao primeiro elemento e lao restante da lista. Se lnão estiver vazio e bmenor que o máximo de l, retorne o máximo seguido por l, caso contrário, retorne bseguido por uma chamada recursiva de f l. Se a lista de entrada estiver vazia, retorne-a.

Raquete 202 bytes

(let((g(λ(L i n)(for/list((c(in-naturals))(l L))(if(= c i)n l))))(ol'()))
(for((c(in-naturals))(i L))(for((d(in-range c(length L)))#:when(>(list-ref L d)i))
(set! ol(cons(g L c(list-ref L d))ol))))ol)

Ungolfed:

(define (f L)
  (let ((replace (λ (L i n)   ; sub-function to replace i-th item in list L with n;
                   (for/list ((c (in-naturals))
                              (l L))
                     (if (= c i) n l))))
        (ol '()))             ; outlist initially empty; 
    (for ((c (in-naturals))               ; for each item in list
          (i L))
      (for ((d (in-range c (length L)))   ; check each subsequent item in list
            #:when (> (list-ref L d) i))  ; if greater, replace it in list
        (set! ol (cons (replace L c (list-ref L d)) ol)))) ; and add to outlist.
    ol))          ; return outlist.

Teste:

(f '(3 1 4 -1 2))

Saída:

'((3 1 4 2 2) (3 2 4 -1 2) (3 4 4 -1 2) (4 1 4 -1 2))

C, 67 bytes

Execução única, 67 bytes ao vivo

j;f(l,i)int*l;{j=i-1;while(i-->0)while(j-->0)l[j]=fmax(l[i],l[j]);}

Etapa única, 78 bytes ao vivo

j;f(l,i)int*l;{j=i-1;while(i-->0)while(j-->0)if(l[j]<l[i]){l[j]=l[i];return;}}

Máximos de cauda, ​​96 bytes em tempo real

x;i;j;f(l,n)int*l;{do{x=0;for(i=0;i<n;i++)for(j=0;j<i;j++)if(l[j]<l[i])l[j]=l[i],x=1;}while(x);}

Python 3 , 103 102 bytes

lambda a:([a[:i]+[max(a[i:])]+a[i+1:]for i in range(len(a))if-~i==len(a)or max(a[i+1:])>a[i]]+[[]])[0]

Experimente online!