fork(1) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6.  
  7.  
  8. int main() {
  9. 	cin.tie(NULL);
  10. 	cout.tie(NULL);
  11. 	ios_base::sync_with_stdio(false);
  12.  
  13. 	int input;
  14. 	cin >> input;
  15.  
  16. 	int arr[1001] = {0};
  17. 	int max = 1;
  18. 	for (int i = 1; i <= input; i++) {
  19. 		cin >> arr[i];
  20. 	}
  21.  
  22. 	int length[1001] = {0};
  23. 	fill_n(length, 1001, 1);
  24. 	//int tracking[1001] = { 0 };
  25. 	int max_idx = 0;
  26.  
  27. 	if (input == 1) {
  28. 		cout << 1 <<"\n" << arr[1];
  29. 	}
  30. 	else {
  31.  
  32. 		for (int i = 1; i <= input; i++) {
  33. 			for (int j = i + 1; j <= input; j++) {
  34. 				if (arr[j] > arr[i]) {
  35. 					if (length[i] + 1 > length[j])
  36. 						length[j] = length[i] + 1;
  37. 					if (max < length[j]) {
  38. 						max = length[j];
  39. 						max_idx = j;
  40. 						//tracking[j] = i;//i번째로 가면 그 다음수를 찾을 수 있다.
  41. 					}
  42.  
  43. 				}
  44.  
  45. 			}
  46. 		}
  47.  
  48.  
  49. 		cout << max << "\n";
  50.  
  51. 		vector <int> vec;
  52.  
  53. 		int i;
  54. 		while (true) {
  55.  
  56.  
  57. 			for (i = max_idx; i >= 1; i--) {
  58. 				if (length[i] == max) {
  59. 					vec.push_back(arr[i]);
  60. 					max_idx=i-1;
  61. 					break;
  62. 				}
  63. 			}
  64. 			max--;
  65.  
  66. 			if (max <= 0) {
  67. 				break;
  68. 			}
  69. 		}
  70.  
  71.  
  72. 		for (i = vec.size() - 1; i >= 0; i--) {
  73. 			cout << vec[i];
  74. 			if (i != 0) {
  75. 				cout << " ";
  76. 			}
  77. 		}
  78.  
  79. 	}
  80. }
Success #stdin #stdout 0s 4440KB
comments (?)
stdin
copy 
2
2 1
stdout
copy 
1
https://ideone.com/5l5bSc
language:
C++14 (gcc 8.3)
created:
5 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!