AGC 024 B - Backfront

B - Backfront

問題
数列からいくつかの数字を前と後ろへ移動させてソートしたい。

数列からいくつかを選んで、前後に動かした時、動かさなかったものは4567のような1ずつ増える数列である。つまりそのような最長の部分列を探したい。
数字の場所のインデックスを持てば、その中で最長の単調増加数列を探せばよい。

問題の芯
とりあえず書いてみる 数列はインデックスを取る

類題
B - Minimum Sum

public static void main(String[] args)
    {
        N = sc.nextInt();
        A = sc.nextIntArray(N);
        int[] rev =  new int[N+1];
        for (int i = 0; i < N; i++)
        {
            rev[A[i] ] = i;
        }
        int maxLen = 1;
        int len = 1;
        for (int i = 1; i < N; i++)
        {
            if(rev[i] < rev[i+1]){
                len++;
            }else{
                maxLen = Math.max(maxLen,  len);
                len = 1;
            }
        }
        maxLen = Math.max(maxLen,  len);
        int res = N - maxLen;
        System.out.println(res);
    }