longest increasing subsequence

This Question Was Asked By Microsoft

Given an array of numbers, find the length of the longest increasing subsequence in the array. The subsequence does not necessarily have to be contiguous.

Write a function solve that have the following parameter(s):
1.) arr = an array

Example
Input:
[0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]
Output:
6

Explanation
An array [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15] will return the longest increasing subsequence length 6 it is (0, 2, 6, 9, 11, 15).

Constraints
• The size of an array should be greater than 0 and less than 800.
• The elements of an array should be greater than 0 and less than 1000.