# Partition it into as few disjoint contiguous increasing subsequences as possible [closed]

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

• This site is for programming contests (i.e., you post programming challenges in questions), general programming questions are off-topic here. Jan 27 '18 at 7:52
• (in other words, because the question is a question, it's off-topic. Counter-intuitive) Jan 27 '18 at 7:52
• Is this a code-golf? Maybe you should clarify and add a code-golf tag. Jan 27 '18 at 8:04
• Is the example answer 2 because the minimal length of any possible B is 2 or because there are 2 such minima? Seems to be some conflict between "your task is to partition it into as few contiguous increasing subsequences as possible" vs "we have Q queries updating single value on A asking minimum number of type B(s) possible" Jan 27 '18 at 9:38
• This challenge needs more test cases. I'd suggest [], [3], [1,2], [2,5], [2,6,3], [1,2,11,12,3,4,9,20,22,10,5,6,14,13]. Jan 27 '18 at 13:42

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


TryItOnline

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


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]


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

• I believe [1,2,8,3,4,3,5,7] should actually not return either 3 or 2 but 1 since there is only a single minimal length partition, [[1,2],[8],[3],[4,3,5],[7]], satisfying the criteria. (Either that or 5 since that's the minimal length) Jan 27 '18 at 14:08
• That may have been what the OP was going for, but the latest revision clearly asks to indicate the smallest number of parts A can be splitted to. Jan 27 '18 at 14:11
• Also, since [1,2,3,4,5],[3] appear as part of the worked example, reordering is clearly allowed. Jan 27 '18 at 14:12
• Ah, hadn't updated since going out.... Jan 27 '18 at 14:13
• It is not; it has been there since revision 1. By contiguous, the OP appears to mean that the partitions consist of consecutive integers, Jan 27 '18 at 14:17