AtCoder Beginner Contest #006 D: トランプ挿入ソート (二分探索・最大増加部分列)

コード

import java.io.IOException;
import java.util.Arrays;

public class Main {

	public static void main(String[] args) throws Exception {
		int N = nextInt();
		int[] cards = new int[N];
		for (int i = 0; i < cards.length; i++) {
			cards[i] = nextInt();
		}

		int[] dp = new int[N + 1];
		Arrays.fill(dp, Integer.MAX_VALUE);
		dp[0] = Integer.MIN_VALUE;

		for (int i = 0; i < N; i++) {
			int j = ~Arrays.binarySearch(dp, cards[i]);
			dp[j] = cards[i];
		}

		int max = 0;
		for (int i = N; i > 0; i--) {
			if (dp[i] <= N) {
				max = i;
				break;
			}
		}
		System.out.println(N - max);

	}

	static int nextInt() {
		int c;
		try {
			c = System.in.read();
			while (c != '-' && (c < '0' || c > '9'))
				c = System.in.read();
			if (c == '-')
				return -nextInt();
			int res = 0;
			while (c >= '0' && c <= '9') {
				res = res * 10 + c - '0';
				c = System.in.read();
			}
			return res;
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		return -1;
	}
}