CSES : Collecting numbers

help
1

Probliem : CSES - Collecting Numbers

 int n;
  cin >> n;
  set<int> s;
  for (int i = 0; i < n; i++){
  	int x;
  	cin >> x;
  	auto it = s.lower_bound(x);
  	if (it != s.begin()){
  		s.erase(prev(it));
  	}
  	s.insert(x);
  }
  cout << (int)s.size(s) << '\n';

Why my solution is wrong. I test it on several cases but it still fails on submission.

2

hey @hell_world
Thanks for sharing your doubt.

Your logic is incorrect. Here is a test case in which your code gives a wrong answer :point_down:

4
2 1 4 3

Please see my code for a correct solution.

int n,i;
cin>>n;
int a[n];
int mark[n+1];
for(i=0;i<n;i++){
    cin>>a[i];
    mark[a[i]]=i;
}
int ans=1;
int prev=-1;
for(i=1;i<=n;i++){
    if(mark[i]<prev){
        ans++;
        
    }
    prev=mark[i];


}
cout<<ans;