# 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 '18 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). – Post Rock Garf Hunter Oct 8 '18 at 7:12
• Suggested test cases: [] => 0,  => 1, [3,2,1] => 1, [1,2,1,2] => 2 – Sok Oct 8 '18 at 8:22
• Would you mind elaborating on the 'score' a bit more? – ouflak Oct 8 '18 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 '18 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. – Max Yekhlakov Oct 8 '18 at 10:08
• @MaxYekhlakov You're right, I don't know how I missed that. – Delfad0r Oct 8 '18 at 11:42
• Your code returns 1 for the empty list, where it should return 0 – Jo King Oct 10 '18 at 7:52
• @Jo King Indeed, I had missed the discussion in the comments. Fixing that right now. – Delfad0r Oct 10 '18 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. – Arnauld Oct 7 '18 at 16:18 • @Arnauld added 5 spaces to your suggestion so that it's now a score 2 – Shieru Asakoto Oct 8 '18 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+

# 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... – ETHproductions Oct 8 '18 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! – mypetlion Oct 9 '18 at 20:55
• Indent with tabs to get a score of 4. – mypetlion Oct 9 '18 at 21:15
• @mypetition: D'oh! Thought this was code golf... editing my answer now. – Chas Brown Oct 10 '18 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 '18 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! – Chas Brown Oct 10 '18 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.) – Misha Lavrov Oct 7 '18 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 '18 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? – Jaden Lee Oct 10 '18 at 2:29
• Yes, since the input is a list of integers – Jo King Oct 10 '18 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. – Syed Hamza Hassan Oct 8 '18 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. – Syed Hamza Hassan Oct 8 '18 at 5:54
• I have updated score and link please check. – Syed Hamza Hassan Oct 8 '18 at 6:12
• Ok, I gave updated. – Syed Hamza Hassan Oct 8 '18 at 6:39
• – Jo King Oct 8 '18 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 '18 at 7:45