fork(1) download
copy 
  1. #include<iostream>
  2. #include<vector>
  3. #include<algorithm>
  4. using namespace std;
  5. int n, num; int a[1001] = { 0 };
  6. int lis[1001] = { 0 }; int index[1001] = { 0 };
  7. vector<int> ans;
  8. int main(void) {
  9. 	scanf("%d", &n);
  10. 	for (int i = 1; i <= n; i++) {
  11. 		scanf("%d", &num);
  12. 		a[i] = num;
  13. 	}
  14. 	lis[1] = a[1]; int d = 1;//첫번째 항은 미리 넣어논다.
  15. 	for (int i = 2; i <= n; i++) {
  16. 		int k = 0;
  17. 		while (a[i] <= lis[d - k]) {
  18. 			k++;
  19. 		}
  20. 		lis[d - k + 1] = a[i];
  21. 		index[a[i]] = lis[d - k];
  22. 		if (k == 0) {//추가만 되었으면 d를 하나 높여준다.
  23. 			d++;
  24. 		}
  25. 	}
  26. 	for (int i = 1; i <= n; i++) {
  27. 		cout << lis[i] << " ";
  28. 	}
  29. 	cout << endl;
  30. 	int maxx = 0;
  31. 	for (int i = 1; i <= n; i++) {
  32. 		if (lis[i] > maxx) {
  33. 			maxx = lis[i];
  34. 		}
  35. 	}
  36. 	int k = maxx;
  37. 	while (k != 0) {
  38. 		//cout << k << " ";
  39. 		ans.push_back(k);
  40. 		k = index[k];
  41. 	}
  42. 	sort(ans.begin(), ans.end());
  43. 	//cout << ans.size() << endl;
  44. 	printf("%d", ans.size());
  45. 	/*for (int i = 0; i < ans.size(); i++) {
  46. 		cout << ans[i] << " ";
  47. 	}*/
  48.  
  49.  
  50.  
  51.  
  52. 	return 0;
  53. }
Success #stdin #stdout 0s 15248KB
comments (?)
stdin
copy 
6
10 20 10 30 20 50
stdout
copy 
10 20 30 50 0 0 
4
https://ideone.com/QDO2Fj
language:
C++ (gcc 8.3)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!