Maximum Length Subsequence from Ticket Prices Array

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:

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.