Maximize length of increasing subsequence possible by appending given sequence

Given a sequence A1,A2,A3,….,An and an empty sequence B. You need to find M minimum number of times this sequence should be appended in B, so that the length of longest increasing sequence in B is maximum possible.

Examples:

Input : [2,1]
Output : 2
Explaination:
If we append the sequence 2 times then the resulting sequence is 
[2,1,2,1] and hence it forms a longest increasing subsequence.

Input : [1,2]
Output : 1
Explaination:
The given sequence already contains longest increasing subsequence,
so we need to append it only 1 time.

Approach:

• If the given sequence contains D distinct elements then the value of M is atmost D.
• If the given sequence contains the D distinct elements then the length of the longest strictly increasing subsequence possible is equal to D.

Intially assume the value of M as 1, and x is equal to the first minimum element. Right is equal to given sequence and Left is initially not defined.

• Step 1: We try to find the minimum possible index of x in Right. If there exists a value equal to x in Right and its index is k then we update the two parts and x as following and go to Step1:
  • Left = given sequence upto k^th index.
  • Right = given sequence from k^th index.
  • x = next minimum element.
• Step 2: If no value matches the x in Right then it should be present in Left. So, we try to find the minimum possible index of x in Left. Let its index is k then we update the two parts, x and M as following and go to Step 1:
  • Left = given sequence upto k^th index.
  • Right = given sequence from k^th index.
  • x = next minimum element.
  • M = M + 1

If x is equal to maximum element of the given sequence then stop. We can maintain the hash for each distinct value and perform the above-mentioned operations efficiently.

Below is the implementation of the approach:

#include <bits/stdc++.h>
using namespace std;

// Returns minimum number 
// of times the sequence 
// A1,A2,A3...,An should 
// be appended.
int count(int arr[], int n)
{
   map <int, vector <int>> m;

   // used to store the index
   // of distinct elements 
   for (int i = 0; i < n; i++) {
       m[arr[i]].push_back(i);
   }

   int prev = n;
   int ans = 0;

   for (auto i : m) {
       if (i.second.back() < prev) {
          ans++;
          prev = i.second[0];
       }
       else
          prev = *lower_bound(i.second.begin(), i.second.end(), prev);
   }
  
   return ans;
}

// Driver Code
int main()
{
  int arr [] = { 1, 3, 2, 1, 2 };
  int n = sizeof(arr) / sizeof(arr[0]);

  // Function call to count 
  // minimum times needed to append  
  cout << count(arr, n);
  return 0;
} 

Output:

2

Time Complexity: O(N*log N)
Space Complexity: O(N)