fork download
copy 
  1. #include <iostream>
  2. #include <stack>
  3. using namespace std;
  4. int arr[1001];
  5. int dp[1001];
  6. stack<int> st;
  7. int main() {
  8. 	int n;
  9. 	cin >> n;
  10. 	for (int i = 1; i <= n; i++) {
  11. 		cin >> arr[i];
  12. 	}
  13. 	int max = 0;
  14. 	for (int i = 1; i <= n; i++) {
  15.         dp[i]=1;
  16. 		for (int j = 1; j < i; j++) {
  17. 			if (arr[i] > arr[j] && dp[j]+1>dp[i]) {
  18. 				dp[i] = dp[j] + 1;
  19. 				if (max < dp[i]) max = dp[i];
  20. 			}
  21. 		}
  22. 	}
  23. 	for (int i = n; i > 0; i--) {
  24. 		if (max == 0) break;
  25. 		if (dp[i] == max) {
  26. 			st.push( arr[i]);
  27. 			max--;
  28. 		}
  29. 	}
  30. 	int stsize = st.size();
  31. 	cout << stsize << '\n';
  32. 	for (int i = 0; i < stsize; i++) {
  33. 		cout << st.top() << ' ';
  34. 		st.pop();
  35. 	}
  36. 	return 0;
  37. }
Success #stdin #stdout 0s 4464KB
comments (?)
stdin
copy 
1
1
stdout
copy 
0
https://ideone.com/aRbRwE
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

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!