fork(10) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. //Find a sorted subsequence of size 3 in linear time
  6. class Solution
  7. {
  8. private:
  9. 	int	seq1;
  10. 	int seq2[2];
  11.  
  12. public:
  13. 	vector<int>	find3IncreasingNumbers(int * arr, int n)
  14. 	{
  15. 		vector<int>	result;
  16. 		if(n < 3)	return result;
  17.  
  18. 		bool seq2Filled = false;
  19. 		seq1 = arr[0];
  20.  
  21. 		for(int i = 1; i < n; ++i)
  22. 		{
  23. 			if(arr[i] < seq1)
  24. 				seq1 = arr[i];
  25. 			else if(arr[i] == seq1)
  26. 				continue;
  27. 			else if(!seq2Filled || arr[i] <= seq2[1]) {
  28. 				seq2[0] = seq1;
  29. 				seq2[1] = arr[i];
  30. 				seq2Filled = true;
  31. 			}
  32. 			else {
  33. 				result.push_back(seq2[0]);
  34. 				result.push_back(seq2[1]);
  35. 				result.push_back(arr[i]);
  36. 				break;
  37. 			}
  38. 		}
  39.  
  40. 		return result;
  41. 	}
  42. };
  43.  
  44. int main() {
  45. 	int arr1[] = {12, 11, 10, 5, 6, 2, 30};
  46. 	int arr2[] = {1, 2, 3, 4};
  47. 	int arr3[] = {4, 3, 1, 2};
  48. 	int arr4[] = {12, 11, 10, 5, 6, 2, 30};
  49. 	Solution so;
  50. 	vector<int>	resultTriple;
  51.  
  52. 	resultTriple = so.find3IncreasingNumbers(arr1, sizeof(arr1)/sizeof(int));
  53. 	if(resultTriple.size())
  54. 		cout<<"Result of arr1 : " <<resultTriple[0]<<" "<<resultTriple[1]<<" "<<resultTriple[2]<<endl;
  55. 	else
  56. 		cout << "Did not find increasing triple in arr1."<<endl;
  57.  
  58. 	resultTriple = so.find3IncreasingNumbers(arr2, sizeof(arr2)/sizeof(int));
  59. 	if(resultTriple.size())
  60. 		cout<<"Result of arr2 : " <<resultTriple[0]<<" "<<resultTriple[1]<<" "<<resultTriple[2]<<endl;
  61. 	else
  62. 		cout << "Did not find increasing triple in arr2."<<endl;
  63.  
  64. 	resultTriple = so.find3IncreasingNumbers(arr3, sizeof(arr3)/sizeof(int));
  65. 	if(resultTriple.size())
  66. 		cout<<"Result of arr3 : " <<resultTriple[0]<<" "<<resultTriple[1]<<" "<<resultTriple[2]<<endl;
  67. 	else
  68. 		cout << "Did not find increasing triple in arr3."<<endl;
  69.  
  70. 	resultTriple = so.find3IncreasingNumbers(arr4, sizeof(arr4)/sizeof(int));
  71. 	if(resultTriple.size())
  72. 		cout<<"Result of arr4 : " <<resultTriple[0]<<" "<<resultTriple[1]<<" "<<resultTriple[2]<<endl;
  73. 	else
  74. 		cout << "Did not find increasing triple in arr4."<<endl;
  75.  
  76.  
  77. 	return 0;
  78. }
Success #stdin #stdout 0s 3480KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Result of arr1 : 5 6 30
Result of arr2 : 1 2 3
Did not find increasing triple in arr3.
Result of arr4 : 5 6 30
https://ideone.com/QefD9V
language:
C++14 (gcc 8.3)
created:
9 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!