// This is a (dynamic programing + binary search) approach which takes O(nlogn) time /* Steps:- -->main LIS function 1.create a ans array and push first element of given array in it. 2.now,from second element of given array traverese till end and to the following if-> current element is bigger than the element at back of ans array push it in the ans array else -> find the index where the curr element can fit in ans array using binary search pass the ans array,size of ans array and curr element as a parameters to binary search function. 3.size of ans array is the length of LIS -->binary search function 1.just do the general binary search ,but if the target element is not found instead of returning -1 return the low. note:- here,low indecates the position where the target should be placed in ans array. */ int give_index_using_binary_search(vector<int> ar, int n, int tar) { int low = 0, high = n - 1; while (low <= high) { int mid = low + (high - low) / 2; if (ar[mid] == tar) return mid; else if (ar[mid] > tar) high = mid - 1; else low = mid + 1; } return low; } int LIS(vector<int> &ar, int n) { vector<int> ans; ans.push_back(ar[0]); for (int i = 1; i < n; i++) { if (ans.back() < ar[i]) ans.push_back(ar[i]); else { int ind = give_index_using_binary_search(ans, ans.size(), ar[i]); ans[ind] = ar[i]; } } return ans.size(); }