Facebook Question - Find the longest increasing subsequence

Problem
You are given an unsorted array of integers. In that array, find the longest increasing subsequence.
For eg. {1, 5, 3, 4, 6, 1, 2, 4, 8, 5 }
In the above, there are multiple increasing sequences:
{1,5}
{3,4}
{3,4,6}
{1,2}
{1,2,4}
{1,2,4,8}
Of the above, last one is the longest sequence.
Write a program to solve the above. It should be linear O(N) time.

Approach
Initialize an array of same length as input. Call it current array. Read the first element and store it in this array. Keep navigating the input array and if the current element is greater than the last element in the current array, then put the value into the current array. If the value is less than the last current array element, then we need to start again. So we need to reset the current array. But hold on, the current array that we have might be the  longest subsequence. So before resetting the array check if the current length of current array is the biggest we found ever. If so copy the array elements into the result array.

current array: {1, 0, 0, 0, 0, 0, 0, 0, 0, 0}
length: 1
maxlength:1

i=1, a[1] = 5 (increasing)
current array: {1, 5, 0, 0, 0, 0, 0, 0, 0, 0}
length: 2
maxlength: 2

i=2, a[2] = 3 (decreasing)
current array: {3, 0, 0, 0, 0, 0, 0, 0, 0, 0}
result: {1, 5}
length: 1
maxlength: 2

i=3, a[3] = 4 (increasing)
current array: {3,4, 0, 0, 0, 0, 0, 0, 0, 0}
result:{1,5}
length: 2
maxlength:2

Solution