There is an array containing prices of n tickets. A number m is defined as the size of a subsequence S of tickets. Each element in the subsequence covers a continuous range of integers. In other words, when the elements in S are sorted, the absolute difference between any two consecutive elements j and j+1 is either 0 or 1.
Find the maximum possible length of subsequence that can be chosen from the given array of ticket prices with satisfying this condition.
Examples:
Input: tickets = [10, 6, 5, 9, 5] Output: 3 Explanation: Valid sub-sequences after sorting are {5, 5, 6} and {10, 9} the maximum length is 3. Input: tickets = [10, 6, 5, 10, 5] Output: 3 Explanation: Valid sub-sequences after sorting are {5, 5, 6} and {10, 10} the maximum length is 3.
Approach:
- Sort the array
- Compare the consecutive 2 elements in the tickets array if their difference is less 1 then increment count
- If their difference is greater then 1 initialize count to 1
- Repeat step 2 until end of the array is reached
Below is the implementation of above approach:
//c++ code to implement //above approach #include <bits/stdc++.h> using namespace std; //function to calculate maximum //size of tickets int maxticketssize(int n, int tickets[]) { //sort it as per the condition sort(tickets, tickets + n); bool flag = 0; //count is used to count the //length of subsequence and //intialised with 1 to include //the present element int count = 1; //maxi stores maximum //sub-sequence length int maxi = 0; for (int i = 0; i < n - 1; i++) { //if difference is less //than or equal to zero //increment count if (tickets[i + 1] - tickets[i] <= 1) { count++; flag = 0; } else { count = 1; //if the same element is //repeats thenincrement i if (flag == 1) { flag = 0; i++; } i--; flag = 1; } //count maximum length //every time and store //in maxi maxi = max(count, maxi); } return maxi; } //driver code int main() { int n = 5; //strore prices in a array int tickets[5] = {8,5,4,8,4}; cout << maxticketssize(n, tickets) <<"\n"; return 0; }
Output:
3
Time Complexity: O(nlogn)
Auxiliary Space: O(1)
Please write comments if you find anything incorrect. A gentle request to share this topic on your social media profile.