forked from Gaurang2908/HacktoberFest2022
-
Notifications
You must be signed in to change notification settings - Fork 0
/
SortedSubsequence.cpp
82 lines (67 loc) · 1.5 KB
/
SortedSubsequence.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
// C++ Program for above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the triplet
void find3Numbers(vector<int>& nums)
{
// If number of elements < 3
// then no triplets are possible
if (nums.size() < 3){
cout << "No such triplet found";
return;
}
// track best sequence length
// (not current sequence length)
int seq = 1;
// min number in array
int min_num = nums[0];
// least max number in best sequence
// i.e. track arr[j] (e.g. in
// array {1, 5, 3} our best sequence
// would be {1, 3} with arr[j] = 3)
int max_seq = INT_MAX;
// save arr[i]
int store_min = min_num;
// Iterate from 1 to nums.size()
for (int i = 1; i < nums.size(); i++)
{
if (nums[i] == min_num)
continue;
else if (nums[i] < min_num)
{
min_num = nums[i];
continue;
}
// this condition is only hit
// when current sequence size is 2
else if (nums[i] < max_seq) {
// update best sequence max number
// to a smaller value
// (i.e. we've found a
// smaller value for arr[j])
max_seq = nums[i];
// store best sequence start value
// i.e. arr[i]
store_min = min_num;
}
// Increase best sequence length &
// save next number in our triplet
else if (nums[i] > max_seq)
{
// We've found our arr[k]!
// Print the output
cout << "Triplet: " << store_min <<
", " << max_seq << ", " <<
nums[i] << endl;
return;
}
}
// No triplet found
cout << "No such triplet found";
}
// Driver Code
int main() {
vector<int> nums {1,2,-1,7,5};
// Function Call
find3Numbers(nums);
}