# Longest Increasing Substring

Given a list of positive integers, write code that finds the length of longest contiguous sub-list that is increasing (not strictly). That is the longest sublist such that each element is greater than or equal to the last.

For example if the input was:

$$\[1,1,2,1,1,4,5,3,2,1,1]\$$

The longest increasing sub-list would be $$\[1,1,4,5]\$$, so you would output $$\4\$$.

Your answer will be scored by taking its source as a list of bytes and then finding the length of the longest increasing sub-list of that list. A lower score is the goal. Ties are broken in favor of programs with fewer overall bytes.

• Is it okay to return true instead of 1? And do we have to handle an empty list?
– Jo King
Oct 8, 2018 at 5:28
• For your first one, whatever meta consensus is on numeral output you may do, I don't recall True being a substitute for 1 but it may be. You should be able to handle the empty list (Output is of course 0). Oct 8, 2018 at 7:12
• Suggested test cases: [] => 0,  => 1, [3,2,1] => 1, [1,2,1,2] => 2
– Sok
Oct 8, 2018 at 8:22
• Would you mind elaborating on the 'score' a bit more? Oct 8, 2018 at 9:58
• @ouflak I'm not sure what more there is to say on the score. Convert your submission to a list of bytes and pass it through your own program and that's your score. If scores are equal, the tie-breaker is the bytecount
– Jo King
Oct 8, 2018 at 10:19

# Pyth, score 2 (8 bytes)

lefSIT.:


Try it here!

Code points [108, 101, 102, 83, 73, 84, 46, 58]. Another shorter solution, leSI#.: scores 3, but its code points are [108, 101, 83, 73, 35, 46, 58], which are very close to a score of 1, actually. Rearranging a bit may help Nevermind, the substrings built-in is .: which cannot be rearranged, so the lowest score must be 2 if the program makes use of it.

### How?

lefSIT.:     Full program. Accepts either a list or a string from STDIN.
.:     Substrings.
f  T       Only keep those that are...
SI        Sorting-Invariant.
le           Length of the last item.


# Haskell, score 2, 66646160 65 bytes

• -2 bytes thanks to Max Yekhlakov
• -1 byte thanks to nimi
• +5 bytes to handle the empty list
foldr1 max.g
g[]=
g(x:y:z)|x>y=1: g(y:z)
g(_:y)|a:b<-g y=1+a:b


Try it online! (verifies itself).

I never thought I could get a score of 2 with Haskell, and yet here I am!

Function g computes the lengths of all the increasing substrings recursively. foldr1 max.g takes the maximum of those lengths (foldr1 max is equivalent to maximum, but with a lower score).

• Looks like the whitespace in 1+a : b is not necessary, so this is 62 bytes. Oct 8, 2018 at 10:08
• @MaxYekhlakov You're right, I don't know how I missed that. Oct 8, 2018 at 11:42
• Your code returns 1 for the empty list, where it should return 0
– Jo King
Oct 10, 2018 at 7:52
• @Jo King Indeed, I had missed the discussion in the comments. Fixing that right now. Oct 10, 2018 at 8:12

# JavaScript (Node.js), score 3, 53 46 bytes score 2, 51 50 bytes

-7 bytes thanks @Arnauld

+5 +4 spaces in exchange of -1 score

a=> a.map($= p=n=>$=(p<=(p=n)?++ x:x=1)<$?$: x)&&$ Try it online! Assumes non-empty input. 61 bytes if empty list must be handled. Score 2 still. a=> a.map($= p=n=>$=(p<=(p=n)?++ x:x=1)<$?$: x)&& a.length&&$


Try it online!

...or 58 if returning false is allowed. Score 2 still.

a=> a.map($= p=n=>$=(p<=(p=n)?++ x:x=1)<$?$: x)&& a>[ ]&&$ • This should work for 46 bytes and the same score. Oct 7, 2018 at 16:18 • @Arnauld added 5 spaces to your suggestion so that it's now a score 2 Oct 8, 2018 at 0:00 # Husk, 5 bytes, score = 2 00000000: bc6d 4cdc 14 ▲mLġ≥  Try it online! It's unlikely to get a score lower than 2 with Husk because ġ1 has a really high codepoint and there needs to be something before it to get the maximum and length. An attempt could be made with trying to use multiple functions but \n would be before any helper functions which has a really low codepoint so anything after it would create an increasing byte-sequence of at least length 2. 1: This seems like the best way to use for the comparison operators would need to follow the various split functions like ↕ (span). ### Explanation ▲mLġ≥ -- example input: [1,1,2,1,1,4,5,3,2,1,1] ġ≥ -- group elements by geq: [[1,1,2],[1,1,4,5],,,[1,1]] mL -- map length: [3,4,1,1,2] ▲ -- maximum: 4  # Retina 0.8.2, 40 bytes, score 3 \d+$*
(?<=(1+)),(?!\1)
¶
T1_
^O
\G,?


Try it online! Link includes itself as byte codes as input. Explanation:

\d+

# Jelly, 8 bytes, score 2

There is probably a score 1 solution somehow...

IṠµṣ-ZL‘


Try it online!

Source code as a list of byte values:

[73, 205, 9, 223, 45, 90, 76, 252]


### How?

IṠµṣ-ZL‘ - Link: list of integers  e.g. [ 1, 1, 2, 1, 1, 4, 5, 3, 2, 1, 1]
I        - increments                    [ 0, 1,-1, 0, 3, 1,-2,-1,-1, 0]
Ṡ       - sign                          [ 0, 1,-1, 0, 1, 1,-1,-1,-1, 0]
µ      - start a new monadic chain (a low byte to stop score being 3)
-    - literal minus one             -1
ṣ     - split at                      [[0, 1], [0, 1, 1], [], [], ]
Z   - transpose                     [[0, 0, 0], [1, 1], 1]
L  - length                        3
‘ - increment                     4


# 05AB1E, score 3 (9 bytes)

Œʒ¥dP}éθg


Can most likely be a score of 2 somehow.

Code points of the program-bytes: [140,1,90,100,80,125,233,9,103] (two sublists of length 3: [1,90,100] and [80,125,233])

Try it online.

Explanation:

Œ            # Sublists
ʒ   }       # Filter by:
¥          #  Take the deltas
d         #  Check for each whether the number is >= 0
P        #  And check if it was truthy for all deltas
é      # Then sort by length
θ     # Take the last element
g    # And take its length as result


# Java (JDK), score 3, 94 bytes

a->{int m=0,p=0,x=0,i=0,n;while(i<a.length){n=a[i++];m=(p<=(p=n)?++x:(x=1)) <m?m:x;}return m;}


Try it online!

Port of my (with suggestions from Arnauld) JS answer. etu in return and hil in while make it impossible to golf to score 2.

for cannot be used here because:

• ;for is ascending
• for cannot be used at the beginning of the lambda body (scope restrictions). It is possible to wrap it with {} but apparently using while saves bytes.
• I was going to suggest possibly using \u in some places, but then you have to have 00 followed by a digit which is 3 anyway... Oct 8, 2018 at 18:32

# Powershell, score 3, 44 bytes

($args|%{$i*=$_-ge$p;$p=$_;(++$i)}|sort)[-1]  Test script: $f = {

(
$args|%{ # for each integer from argument list$i*=$_-ge$p # -ge means >=.
# This statement multiplies the $i by the comparison result. # A result of a logical operator is 0 or 1. # So, we continue to count a current sequence or start to count a new sequence$p=$_ # let$p stores a 'previous integer'
(++$i) # increment and return incremented as length of a current sequence }|sort # sort lengthes )[-1] # take last one (maximum) } @( ,(4, 1,1,2,1,1,4,5,3,2,1,1) ) | % {$e,$a =$_
$r = &$f @a
"$($r-eq$e):$r"
}


Output:

True: 4


Explanation:

• The script takes integers as argument list (spaltting).
• Each integer maps by a function to legnth of contiguous sub-list that is increasing (not strictly). Then the script sorts lengthes and take a last (maximum) (...|sort)[-1].

## Powershell 6, score 3, 43 bytes

$args|%{$i*=$_-ge$p;$p=$_;(++\$i)}|sort -b 1


Same as above. One difference: sort -b 1 is shortcut for sort -Bottom 1 and means 1 element from the end of sorted array. So we need not an index [-1].

# Stax, score 3 (15 bytes)

Z|[F|]F:^!C_%|M


Run and debug it

# Python 2, score 5, 87 bytes score 2, 1019392 101 bytes

lambda a,m=1,o=:max(reduce(lambda B,c:[B[:-m]+[B[-m]+m],B+o][c>c[m]],zip(a,a[m:]), o)) *(a>[ ])


Try it online!

Ooops! Thought this was code-golf first time through...

• Score of 5. Try it online! Oct 9, 2018 at 20:55
• Indent with tabs to get a score of 4. Oct 9, 2018 at 21:15
• @mypetition: D'oh! Thought this was code golf... editing my answer now. Oct 10, 2018 at 1:31
• Funny that removing the m=1,o= part doesn't end up saving any bytes once we reduce the score
– Jo King
Oct 10, 2018 at 3:39
• @Jo King: Chuckle! I kept hoping that by squirming in that way, I could chip off another byte; but no such luck! Oct 10, 2018 at 4:30

# Dyalog APL, score 2, 20 bytes

{⍵≡⍬:0⋄⌈/≢¨⍵⊂⍨1,2>/⍵}


Try it online!

# Wolfram Language (Mathematica), score 3, 45 bytes

Max[Length/@SequenceCases[#,x_/;OrderedQ@x]]&


Try it online!

SequenceCases and OrderedQ by themselves give a score of 3, so the score can't be improved without changing the approach significantly.

• The correct way to use patterns would have us do Max[Length/@SequenceCases[#,_?OrderedQ]]&, but _?Or is an increasing subsequence of length 4. (As is _?AnyCamelCaseCommand.) Oct 7, 2018 at 17:10

# Java (JDK), 126 bytes, Score 6

Golfed

private static int l(byte[] o){int m=0;int c=1;int p=0;for(byte i:o){if(m<c){m=c;}if(i>=p){p= i;c++;}else{c=1;p=0;}}return m;}


Ungolfed

private static int longest(byte[] input) {
int maxc = 0;
int consec = 1;
int prev = 0;
for (byte i : input) {
if (maxc < consec) {
maxc = consec;
}
if (i >= prev) {
prev = i;
consec++;
}
else {
consec = 1;
prev = 0;
}
}
return maxc;
}


Input

[112, 114, 105, 118, 97, 116, 101, 32, 115, 116, 97, 116, 105, 99, 32, 105, 110, 116, 32, 108, 40, 98, 121, 116, 101, 91, 93, 32, 111, 41, 123, 105, 110, 116, 32, 109, 61, 48, 59, 105, 110, 116, 32, 99, 61, 49, 59, 105, 110, 116, 32, 112, 61, 48, 59, 102, 111, 114, 40, 98, 121, 116, 101, 32, 105, 58, 111, 41, 123, 105, 102, 40, 109, 60, 99, 41, 123, 109, 61, 99, 59, 125, 105, 102, 40, 105, 62, 61, 112, 41, 123, 112, 61, 32, 105, 59, 99, 43, 43, 59, 125, 101, 108, 115, 101, 123, 99, 61, 49, 59, 112, 61, 48, 59, 125, 125, 114, 101, 116, 117, 114, 110, 32, 109, 59, 125]

• Shouldn't byte be int, since byte would be restricted to 8 bits?
– Jo King
Oct 8, 2018 at 10:17
• @JoKing I am not exactly sure what you mean. Do you mean that I should change the byte class to int class? Oct 10, 2018 at 2:29
• Yes, since the input is a list of integers
– Jo King
Oct 10, 2018 at 2:47

Kotlin, Score 6, 119 bytes

 fun x(a : IntArray){var m=1;var k=0;var d=1;while(k<a.size-1){if(a[k]<=a[k+1])m++;else{if(d<m)d=m;m=1};k++};println(d)}


Try Online

Explanation

1. Step 1: Check for previous value to next value
2. Step 2: If previous value is less or equal then add plus 1 keep doing while condition is true
3. Step 3: check previous count with next count, keep highest count in variable d.
• Ok, i got it, i will edit it shortly. Oct 8, 2018 at 5:44
• Please check, i have made a function in which input can be given. As per my sample string answer would be [2,4,5,6,7,7,7] Score is 7. Oct 8, 2018 at 5:54
• I have updated score and link please check. Oct 8, 2018 at 6:12
• Ok, I gave updated. Oct 8, 2018 at 6:39
• – Jo King
Oct 8, 2018 at 6:49

# Kotlin, Score 4, 67 bytes

{a:IntArray->var i=0;var p=0;a.map{if(it<p){i=0};p=it;(++i)}.max()}


Main idea is: Transform each integer to length of contiguous sub-sequences that is increasing (not strictly). Return maximum.

• a.map{...} - for each integer in the array do
• if(it<p){i=0} - if current integer is less then a previous integer, then reset counter
• p=it - store current integer in the previous
• (++i) - increment counter and return value of the expression
• .max() - get maximun of all length

# Ruby, 64 bytes

->e{e.size.downto(1).find{|l|e.each_cons(l).find{|c|c==c.sort}}}


Try it online!

• Note that this is not code-golf. Your current score is 6. Also, your code does not handle the empty list (where the output should be 0)
– Jo King
Oct 10, 2018 at 7:45

# Brachylog, score: 2 (8 bytes)

⊇L≤₁&sLl


Try it online!

This code, according to Brachylog’s code page, is the following string of char codes / integers:

[08, 4C, 03, 80, 26, 73, 4C, 6C]
[8, 76, 3, 128, 38, 115, 76, 108]


Which results in a score of 2.

### Explanation

⊇L         L is a sublist of the input (trying from longest to shortest)
L≤₁       L is increasing
&sL    L is also a contiguous sublist of the input
l   Output the length of L


We need to use ⊇ to get the longest sublists first and then check that it is contiguous with s, because s does not try them longest first (see this Brachylog tip).

# Go, score 4, 172 bytes

type y=int
type x=[]y
func f(q x)y{l,o:=*new(x),*new(x)
for _,e:=range q{n:=len(o)
if n>0&&o[n-1]>e{if len(l)<n{l=o}
o=append(*new(x),e)}else{o=append(o,e)}}
return len(l)}


Attempt This Online!

I'm pretty sure this is the absolute minimum this bit of code can achieve, because =int is ascending in terms of value.

If you change y to be rune, and x=[] y you then get hung up on \nfor. Unless someone finds a way to make case-insensitive keywords in Go, then 4 is the minimum score.