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 kth index.
- Right = given sequence from kth 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 kth index.
- Right = given sequence from kth 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)