Partition it into as few disjoint contiguous increasing subsequences as possible

Question

Specification

This challenge is simple to state: your input is a non-empty array of nonnegative integers, and your task is to partition it into as few substrings as possible, such that each substring is a permutation of a consecutive integer range. More formally, if the input array is A, then the output is minimum number of partition of A into B(s):

• Each arrays B form a partition of A into substrings. Inductively, this means that either B is the singleton array containing 1 element from A, or the elements of B is a subsequence of A, which when sorted are contiguous like x,x+1,x+2,...
• The number of arrays B is minimal.

Example

Consider the input array A = [1,2,3,4,3,5].
Output is 2
One possible minimal partitions are B = [1,2,3],[4,3,5]. That's the only partition to 2 substrings.

{4,3,5} in sorted order is {3,4,5} which is contiguous.

Input

An array of integers A.

Output

A number, indicate the smallest number of parts A can be splitted to.

Winning criteria

Your submissions will be scored in bytes, with less bytes being better.

Answer 1

Kotlin, 91 bytes

fold(mutableListOf<Int>()){r,i->r.indexOfFirst{it<i}.let{if(it<0)r+=i else r[it]=i
r}}.size

Beautified

fold(mutableListOf<Int>()) {r,i->
    r.indexOfFirst { it<i }.let {
        if (it<0) r+=i else r[it]=i
        r
    }
}.size

Test

fun MutableList<Int>.f() =
fold(mutableListOf<Int>()){r,i->r.indexOfFirst{it<i}.let{if(it<0)r+=i else r[it]=i
r}}.size

fun main(args: Array<String>) {
    val i = mutableListOf(1,2,3,4,3,5)
    println(i.f())
}

TIO

TryItOnline

Answer 2

JavaScript (ES6), 82 bytes

f=(a,n=Math.min(...a),i=a.indexOf(n))=>1/a[0]?i<0?1+f(a):f(a,a.splice(i,1)[0]+1):1

Answer 3

Haskell, 139 bytes

import Data.List
l=length
q(x:r)=map([x]:)(q r)++[(x:y):v|(y:v)<-q r]
q[]=[[]]
s(x:y)=x+l y==last(x:y)
f x=minimum[l y|y<-q x,all(s.sort)y]

Answer 4

Jelly, 9 bytes

Œ!Iċ€1ṀạL

Try it online!

How it works

Œ!Iċ€1ṀạL  Main link. Argument: A (array)

Œ!         Take all permutations of A.
  I        Increments; compute the forward differences of each permutation.
   ċ€1     Count the number of 1's i each array of deltas.
      Ṁ    Take the maximum.
        L  Compute the length of A.
       ạ   Take the absolute value of the difference of the maximum and the length.