Google Interview Question

Given an array of integers, write a function to find the longest increasing subsequence. Implement your solution with a time complexity better than O(n^2).