Given an integer array ‘A’, find the length of its longest increasing subsequence (LIS). LIS is a sub-array of the given integer array where the elements are sorted in a monotonic/strict increasing order.
Input Format:
Input 1: Integer input ‘n'(1<=input1<=1000)
Input 2: Integer array ‘A’ input, containing ‘n’ integers.
Output Format:
Return the length of its LIS.
Example 1:
Input 1: 3
Input 2: {1,3,2}
Output:
2
Explanation:
{1,2} and {1,3} are the longest increasing subsequence of {1,3,2}. The length of both LIS is 2.
Example 2:
Input 1: 5
Input 2: {41,18467,6334,26500,19169}
Output:
3
Explanation:
{41,6334,26500}, {41,18467,26500}, etc are the longest increasing subsequences of {41,18467,6334,26500,19169}, In all of the cases, the length of LIS is 3.
