2nd code O(n) all pass.. 1st code O(n^2)


#1

// ///// 1st O(n^2) all test case pass
// int Solution::lis(const vector &A) {
// int n=A.size();
// if(n==1)return 1;

// int lis[n];
// int i,j;

// int ans=1;
// lis[0]=1;
// for(i=1;i<n;i++)
// { lis[i]=1;
// for(j=0;j<i;j++)
// if(A[i]>A[j] && lis[i]<lis[j]+1)
// { lis[i]=lis[j]+1; ans=max(ans,lis[i]);
// }
// }

// // ans=0;
// // for(i=0;i<n;i++)
// // ans=max(ans,lis[i]);// if(ans<lis[i])
// // // ans=lis[i];
// return ans;
// }

//////// 2nd code O(n) all pass…
int Solution::lis(const vector &nums) {
if(nums.size()==1)return 1;

vector<int> min;
for(int num : nums){
	auto it = lower_bound(min.begin(), min.end(), num);
	if(it!=min.end())
		*it=num;
	else
		min.push_back(num);
    }
return min.size();

}


#3

Can you please explain your second solution?
It looks elegant.


#4

Lower Bound works in log(n) time so your second solution works in O(nlog(n)) time.