# Raise a single number

## Introduction

Suppose you want to compute the tail maxima of a list of numbers, that is, the maximum of each nonempty suffix. One way to do it is to repeatedly choose one number and replace it by a higher number occurring after it, until this is not possible anymore. In this challenge, your task is to perform one step of this algorithm.

Your input is a list of integers L, which may be empty. Your output shall be the list L where exactly one number Li has been replaced by another Lj, where Li < Lj and i < j.

In other words, you shall replace one number with a higher number that occurs after it.

You can choose i and j freely among all valid pairs, and the choice can be nondeterministic.

If such i and j do not exist (i.e. L is non-increasing), your output shall be L unchanged.

## Example

Consider the input L = [ 3, 1, 4, -1, 2 ]. The possible operations are to replace 3 by 4, replace 1 by 4, replace 1 by 2, or replace -1 by 2. Thus the possible outputs are:

 [  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)]


If you repeat the operation enough times, the end result will be [4,4,4,2,2], which is precisely the list of tail maxima of L.

## Rules and scoring

You can write a full program or a function. In the latter case, you can modify the input in place instead of returning a new array, if your language allows that. Input and output formats are flexible within reason.

The lowest byte count wins.

## Test cases

All possible outputs are shown.

[] -> []
[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), 414039 38 bytes

Saved a byte thanks to @Neil, another thanks to @user81655

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


Just when it seems reduceRight might finally have a chance, .map shows up yet again...

• x=>x.map(c=>c<x[++i]&!d?x[d=i]:c,d=i=0)?
– Neil
Mar 24, 2017 at 21:43
• Conditionals are evaluated left-to-right, which means x=>x.map(c=>c<x[++i]>d?x[d=i]:c,d=i=0) (38 bytes) should work. Mar 25, 2017 at 9:29
• @user81655 That's amazing :-) Mar 28, 2017 at 13:05

# Mathematica, 37 bytes

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


Pure function taking a list of real numbers even, and returning a list of real numbers. Looks for the first pair of consecutive entries in the "wrong" order, and replaces the first of that pair with the second. Nice default behavior of /. means that it returns the input unaltered when appropriate.

Amusing side note: if we replace b<c with !OrderedQ[{c,b}], then the function works on strings (and really any data type once the appropriate ordering is described). For example, #/.{a___,b_,c_,d___}/;!OrderedQ[{c,b}]:>{a,c,c,d}& on input {"programming", "puzzles", "code", "golf"} returns {"puzzles", "puzzles", "code", "golf"}.

• A caveat for the side note: Mathematica's canonical ordering of strings is weird. Mar 24, 2017 at 21:00
• How so, Martin Ender? Mar 24, 2017 at 21:09
• Just try Sort[FromCharacterCode /@ Range[32, 127]]. It gets weird once you have strings with multiple words, because then it ignores spaces and stuff. Mar 24, 2017 at 21:19

## JavaScript (ES6), 4339 38 bytes

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


Outputs by modifying the array in-place. Edit: Saved 4 bytes thanks to @ETHproductions. Saved 1 byte thanks to @user81655.

• I think you can do with a=>a[i=0,a.findIndex(e=>e<a[++i])]=a[i] for 39. Mar 24, 2017 at 22:44
• Another approach for 40B: a=>a.map((_,b)=>Math.max(...a.slice(b)))
– Luke
Mar 24, 2017 at 23:38
• @Luke I think you're misunderstanding the challenge; the point is to only make one of the integers in the array larger. Mar 24, 2017 at 23:52
• @ETHproductions Thanks for returning the favour, now the honours are even!
– Neil
Mar 25, 2017 at 0:30
• I think you might be able to replace findIndex with some (38 bytes): a=>a[i=0,a.some(e=>e<a[++i])*i-1]=a[i] Mar 25, 2017 at 9:20

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


Try it online!

Look through the list for consecutive elements a,b with a<b and changes them to b,b.

Improved from 37 bytes:

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

• I think f(a:r@(b:_))=max(b:r)(a:f r) works and is two bytes shorter. Mar 26, 2017 at 0:42
• @ØrjanJohansen That's a beautiful method! I think you should post it as your own answer. I wasn't sure at first it would handle ties correctly, but I see now it works because f r >= r.
– xnor
Mar 28, 2017 at 0:04
• Thanks, I've done so! Mar 28, 2017 at 1:22

# Jelly, 13 11 bytes

ṫJṀ€ż¹ŒpQ-ị


Replaces the rightmost of all possible numbers.

Try it online!

### How it works

ṫ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+


Try it online!

I'm not a huge fan of this solution. It seems horribly inefficient to me. Particularly the whY>d* and 0h+ sections.

# Python 2, 139134 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


Terribly long, but it's a first attempt.

-5 bytes thanks to TemporalWolf
-41 (!!) bytes thanks to Value Ink

• [1,2] gives [2,1] instead of [2,2] Mar 24, 2017 at 21:37
• @TemporalWolf Yeah, I misread the challenge. No bytes saved or lost, will fix. Mar 24, 2017 at 21:37
• You can remove the return before your inner print and use a \t tab instead of extra space for the inner loop. Also, you can drop the 0 in exit() for an extra one. Should bring you down to 132. Mar 24, 2017 at 21:52
• a[i+1:j]+[a[j]]+a[j+1:] can be reduced to a[i+1:] to bring it down to 119... I can't actually figure out what that is supposed to do. Mar 24, 2017 at 22:04
• if a[i]<a[j]:a[i]=a[j];print a;exit() is even shorter. Heck, it's better to do for j in a[i+1:]:\n\tif a[i]<j:a[i]=j;print a;exit() Mar 24, 2017 at 23:00

# MATL, 13 bytes

ttd0>fX>Q)2M(


Try it online!

### Explanation

The following two conditions are equivalent:

1. There is a number that has a higher number to its right
2. There is a number that has a higher number immediately to its right

The code uses condition 2, which is simpler. It computes consecutive increments and finds the last positive one, if any. For the two involved entries, it writes the value of the second entry into the first.

This trick is used to handle the case when no substitution can be done. Note also that MATL indexing is 1-based.

Let's use input [3,1,4,-1,2] as an example.

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]


This is based on the answer by xnor, who suggested I post it myself.

EDIT: xnor found a byte to save.

f(a:r@(b:_))=max(b:r)$a:f r f e=e  Try it online! Basically, I observed that the branching of xnor's method always ends up choosing whichever of the branch expressions is largest, since Haskell uses lexicographic ordering for lists. (The case when a==b also works because f r>=r, which can be proved separately by induction.) Put differently, whenever b:r > a:f r, then b:r is a correct answer, and otherwise we can recurse to a:f r. So instead of checking a<b in advance, I just calculate both expressions and take the maximum. This could give an exponential blowup, although Haskell's laziness avoids that unless a and b are equal. • Looks like max(b:r)$a:f r saves a byte.
– xnor
Mar 28, 2017 at 1:28

# 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


Mutates the original array (list) given to it. I'm unhappy that this isn't a lambda and I'm sure there are better optimizations; I'll hopefully address those later.

### Brief explanation

It takes the max of the array past the current element (starting with the zeroth). It then compares this to the element itself: if the max is greater, replace the current element with it and stop, otherwise, increment by one and keep trying that.

# 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}}


Try it online!

# C, 47 bytes

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


Recursive implementation taking as its input a pointer to the first element of an array, and the length of the array. Modifies the array in place.

## 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).


First clause replaces the first element of the list with the maximum value of the rest of the list, but only if this max is bigger. The second clause recursively calls the predicate for the tail of the list. If none of these clauses succeed, the third clause simply returns the input.

This return just one of the possible solutions. It's trivial to find all of them with very similar code, but then the case where no change is possible takes a lot more bytes to handle.

Example:

?- 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;}}


Call with:

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

Try it online -1 byte thanks to @TemporalWolf
-25 bytes thanks to @ValueInk
-7 bytes thanks to @Cole

Function that mutates input array

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


If there was no need to stop after first iteration, it would be a bit prettier

• This appears not to work. Try [1, 3, 5, 7]; it returns [3, 3, 5, 7]. Mar 24, 2017 at 21:31
• A[i]<y and => y>A[i]and saves 1 Mar 24, 2017 at 21:31
• @HyperNeutrino If I inderstand task right, that is valid outut Mar 24, 2017 at 21:36
• Consider r=[y for y in A[i+1:]if y>A[i]]\n if r:A[i]=r[0];break to drop your score to 96! Mar 24, 2017 at 23:12
• Might I suggest what I suggested for one of the other Python answers: convert what you have to a function which mutates the original array so that you can avoid printing and input().
– cole
Mar 25, 2017 at 7:35

# Python 2, 60 bytes

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


Try it Online!

Explanation: Recursively checks if a given element is less than the max element in the rest of the list. If so, returns the list with max replacing the first element.

# TI-Basic, 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


Explanation:

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

Input integers are passed as arguments to the script.

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


Breakdown:

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);  ## Breakdown 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


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


Usage example: f [1,1,2,1] -> [2,1,2,1]. Try it online!.

If the input list has at least one element, bind b to the first element and l to the rest of the list. If l is not empty and b less than the maximum of l, return the maximum followed by l, else return b followed by a recursive call of f l. If the input list is empty, return it.

## Racket 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.


Testing:

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


Output:

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


# C, 67 bytes

Single Run, 67 bytes Live

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


Single Step, 78 bytes Live

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;}}


Tail Maxima, 96 bytes Live

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]


Try it online!