Submission #643832

---

Source Code Expand

import java.util.*;
public class Main
{
	Scanner cin = new Scanner(System.in);
	public void solve()
	{
		int N = cin.nextInt();
		int[] c = new int[N];
		int[] dp = new int[N + 1];
		for(int i = 0;i < N + 1;i++)
			dp[i] = Integer.MAX_VALUE;
		for(int i = 0;i < N;i++)
		{
			c[i] = cin.nextInt();
		}
		int ans = 0;
		for(int i = 0;i < N;i++)
		{
			int index = Arrays.binarySearch(dp,c[i]);
			if(index < 0)index = -(index + 1);
			dp[index] = c[i];
		}
		for(int i = 0;i < N;i++)
		{
			if(dp[i] == Integer.MAX_VALUE)continue;
			ans++;
		}
		System.out.println(N - ans);
	}
	public static void main(String[] args)
	{
		new Main().solve();
	}
}

Submission Info

Judge Result