### Longest Increasing Subsequence Dynamic Programming $O(n^{2})$

What is the longest increasing subsequence? Given: 1 -> 1 [len = 1] Given: 2 3 -> 2 3 [len = 2] Given: 3 2 -> 2 or 3 [len = 1] Given: 3 2 1 -> 1 or 2 or 3 [len = 1] Given: 1 2 3 -> 1 2 3 [len = 3] Given: 9 8 7 1 2 3 4 0 -> 1 2 3 4[len = 4] What is the brute force method run time? is it $O(n^{2})$?
    // /Users/cat/myfile/bitbucket/java/LongestIncreasingSubsequence.java
// Dynamic programming algorithm solves Longest Increasing Subsequence
// with complexity O(n^2)
public static int LISDP(Integer[] array) {
int len = array.length;
// initialize array to 1
int[] maxlist = new int[len];
for(int i=0; i < len; i++)
maxlist[i] = 1;

for(int i=1; i < len; i++) {
for(int j=0; j m)
m = maxlist[i];
}
return m;
}


### Longest Increasing Subsequence Recursion $O(2^{n})$

    //Find the longest increasing subsequence integers
//{2, 4, 1, 5} => 2->4->5
//{2, 4, 1, 2, 3} => 1->2->3
//L[i] = 1 + Max(L[i-1]) where j < i && arr[j] < arr[i]
public static int LISRecursion(int[] array, int len)
{
if(len == 1)
return 1;
else
{
int max = 1;
for(int i=1; i < len; i++)
{
int m = LISRecursion(array, i);
if(array[i-1] < array[len-1])
max = Math.max(max, m+1);
}
System.out.println();
return max;
}
}