# Longest Increasing Subsequence

QUESTION

Given a sequence, find the length of the longest increasing subsequence from a given sequence .\nThe longest increasing subsequence means to find a subsequence of a given sequence in which the subsequence’s elements are in sorted order, lowest\nto highest, and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous, or unique.\n\nNote: Duplicate numbers are not counted as increasing subsequence.\n\nFor example:\n length of LIS for \n{ 10, 22, 9, 33, 21, 50, 41, 60, 80 } is 6 and LIS is {10, 22, 33, 50, 60, 80}.\n\n \n\nInput:\n\nThe first line contains an integer T, depicting total number of test cases. \nThen following T lines contains an integer N depicting the size of array and next line followed by the value of array.\n\n\nOutput:\n\nPrint the Max length of the subsequence in a separate line.\n\n\nConstraints:\n\n1 T 40\n1 N 1000\n0 A[i] 300\n.

“TESTCASE_1”: “1\n16\n0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15\n###—###SEPERATOR—###—\n6”, “TESTCASE_2”: “1\n8\n0 4 8 16 20 24 28 32\n###—###SEPERATOR—###—\n8”, “TESTCASE_3”: “0\n###—###SEPERATOR—###—\n0”, “TESTCASE_4”: “0\n###—###SEPERATOR—###—\n0”, “TESTCASE_5”: “0\n###—###SEPERATOR—###—\n0