You are viewing a single comment's thread. Return to all comments →
weak testcases.... my code fails on:- 1 2 2 answer should be 2, but it comes out to be 1... still my code got AC.
#include <bits/stdc++.h> using namespace std; int max(int x,int y) { if(x>y) return x; else return y; } // Complete the longestIncreasingSubsequence function below. /// O(n^2) solution:- // int longestIncreasingSubsequence(vector<int> ar) { // int p1,p2,i,n; // n=ar.size(); // p1=0; // p2=1; // vector<int> ar2(n); // for(i=0;i<n;i++) // ar2[i]=1; // while(p1<p2&&p2<n) // { // if(ar[p1]<ar[p2]) // { // ar2[p2]=max(ar2[p1]+1,ar2[p2]); // } // p1++; // if(p1==p2) // { // p2++; // p1=0; // } // } // int ans = INT_MIN; // for(i=0;i<n;i++) // { // if(ans<ar2[i]) // ans = ar2[i]; // } // return ans; // } ///O(nlogn) solution:- int binarySearch(vector <int> &arr, int l, int r, int x) { // if (r >= l) { // int mid = l + (r - l) / 2; // if (arr[mid] >= x) // return mid; // if (arr[mid] > x) // return binarySearch(arr, l, mid - 1, x); // return binarySearch(arr, mid + 1, r, x); // } // return -1; while(r-l>1) { int mid = l+(r-l)/2; if(arr[mid]>=x) r=mid; else l=mid; } return r; } int longestIncreasingSubsequence(vector<int>ar) { vector <int> ar2; int i,x,j; int n = ar.size(); ar2.push_back(ar[0]); for(i=1;i<n;i++) { int y = ar2.size(); if(ar[i]>ar2[y-1]) ar2.push_back(ar[i]); else { int z = binarySearch(ar2,-1,y-1,ar[i]); ar2[z] = ar[i]; } } int ans = ar2.size(); return ans; } int main() { ofstream fout(getenv("OUTPUT_PATH")); int n; cin >> n; cin.ignore(numeric_limits<streamsize>::max(), '\n'); vector<int> arr(n); for (int i = 0; i < n; i++) { int arr_item; cin >> arr_item; cin.ignore(numeric_limits<streamsize>::max(), '\n'); arr[i] = arr_item; } int result = longestIncreasingSubsequence(arr); fout << result << "\n"; fout.close(); return 0; }
The Longest Increasing Subsequence
You are viewing a single comment's thread. Return to all comments →
weak testcases.... my code fails on:- 1 2 2 answer should be 2, but it comes out to be 1... still my code got AC.