# Find the length of longest increasing subsequence in an array

Find the length of longest increasing subsequence in an array.
Example:
For input array:  {12, 18, 7, 34, 30, 28, 90, 88}
length of longest increasing subsequence is 4.

## Algorithm/Insights

This problem can be solved by applying dynamic programming strategy as explained below:
1. Create an array lisLength, of length same as input array length, to store longest increasing subsequence defined as:
lisLength[i] = length of longest increasing subsequence in the array [0..i] including ith element
2. Initialize lisLength[i] to 1.
3. The lisLength array is then updated one element by element:
lisLength[i] = Max(lisLength[j]) + 1, for all values of j where input[j] < input[i] and j < i

How this works:
For j = 0 to i-1, if input[j] < input[i], then input[i] can be added to the longest increasing subsequence which is formed from array elements 0 to j.
Therefore, to find longest increasing subsequence in 0..i, lisLength[i], we need the Max(lisLength[j]) value which satisfies this condition.
If there is no such j, then longest increasing subsequence in input array 0..i, lisLength[i] = 1 which is formed by adding only ith element.

Example: lisLength[] : [1, 0, 0, 0, 0, 0, 0, 0]

i = 1: lisLength = 1
j = 0: input = 12 < input = 18, also lisLength = 1 < lisLength + 1 = 2, so we update:
lisLength = lisLength + 1 = 2
lisLength[] : [1, 2, 0, 0, 0, 0, 0, 0]

i = 2: lisLength = 1
j = 0: input = 12 > input = 7
j = 1: input = 18 > input = 7
lisLength[] : [1, 2, 1, 0, 0, 0, 0, 0]

i = 3: lisLength = 1
j = 0: input = 12 < input = 34, also lisLength = 1 < lisLength + 1 = 2, so we update:
lisLength = lisLength + 1 = 2
j = 1: input = 18 < input = 34, also lisLength = 2 < lisLength + 1 = 3, so we update:
lisLength = lisLength + 1 = 3
j = 2: input =  7 < input = 34, but lisLength = 3 > lisLength + 1 = 2, so lisLength is not updated.
lisLength[] : [1, 2, 1, 3, 0, 0, 0, 0]

i = 4: lisLength = 1
j = 0: input = 12 < input = 30, also lisLength = 1 < lisLength + 1 = 2, so we update:
lisLength = lisLength + 1 = 2
j = 1: input = 18 < input = 30, also lisLength = 2 < lisLength + 1 = 3, so we update:
lisLength = lisLength + 1 = 3
j = 2: input =  7 < input = 30, but lisLength = 3 > lisLength + 1 = 2, so lisLength is not updated.
j = 3: input = 34 > input = 30
lisLength[] : [1, 2, 1, 3, 3, 0, 0, 0]

i = 5: lisLength = 1
j = 0: input = 12 < input = 28, also lisLength = 1 < lisLength + 1 = 2, so we update:
lisLength = lisLength + 1 = 2
j = 1: input = 18 < input = 28, also lisLength = 2 < lisLength + 1 = 3, so we update:
lisLength = lisLength + 1 = 3
j = 2: input =  7 < input = 28, but lisLength = 3 > lisLength + 1, so lisLength is not updated.
j = 3: input = 34 > input = 28
j = 4: input = 30 > input = 28
lisLength[] : [1, 2, 1, 3, 3, 3, 0, 0]

i = 6: lisLength = 1
j = 0: input = 12 < input = 90, also lisLength = 1 < lisLength + 1 = 2, so we update:
lisLength = lisLength + 1 = 2
j = 1: input = 18 < input = 90, also lisLength = 2 < lisLength + 1 = 3, so we update:
lisLength = lisLength + 1 = 3
j = 2: input =  7 < input = 90, but lisLength = 3 > lisLength + 1, so lisLength is not updated.
j = 3: input = 34 < input = 90, also lisLength = 3 < lisLength + 1 = 4, so we update:
lisLength = lisLength + 1 = 4
j = 4: input = 30 < input = 90, but lisLength = 4 = lisLength + 1, so lisLength is not updated.
j = 5: input = 28 < input = 90, but lisLength = 4 = lisLength + 1, so lisLength is not updated.
lisLength[] : [1, 2, 1, 3, 3, 3, 4, 0]

i = 7: lisLength = 1
j = 0: input = 12 < input = 88, also lisLength = 1 < lisLength + 1 = 2, so we update:
lisLength = lisLength + 1 = 2
j = 1: input = 18 < input = 88, also lisLength = 1 < lisLength + 1 = 3, so we update:
lisLength = lisLength + 1 = 3
j = 2: input =  7 < input = 88, but lisLength = 3 > lisLength + 1, so lisLength is not updated.
j = 3: input = 34 < input = 88, also lisLength = 3 < lisLength + 1 = 4, so we update:
lisLength = lisLength + 1 = 4
j = 4: input = 30 < input = 88, but lisLength = 4 = lisLength + 1, so lisLength is not updated.
j = 5: input = 28 < input = 88, but lisLength = 4 = lisLength + 1, so lisLength is not updated.
j = 6: input = 90 > input = 88
lisLength[] : [1, 2, 1, 3, 3, 3, 4, 4]

Solution: Maximum value in lisLength array = 4.

Time complexity of this solution is O(n^2).

Here is a solution with O(nlogn) complexity:
Longest Increasing Subsequence O(nlogn) solution

## Code Snippet

```
package com.ideserve.questions.saurabh;

/**
* <b>IDeserve <br>
* Find the length of longest increasing subsequence in an array
*
* @author Saurabh
*/
public class LongestIncreasingSubsequence {

public static int longestIncreasingSubsequence(int[] input) {

if(input == null || input.length == 0) {
return 0;
}

int n = input.length;
// lisLength[i] = Length of Longest Increasing Subsequence in input[0..i]
int[] lisLength = new int[n];
int maxLength = 1;
lisLength = 1;
for (int i = 1; i < n; i++) {
lisLength[i] = 1;
for (int j = 0; j < i; j++) {
if (input[i] > input[j] && lisLength[i] < lisLength[j] + 1) {
lisLength[i] = lisLength[j] + 1;
}
}
// Update the length of longest increasing subsequence found till now
if(maxLength < lisLength[i]) {
maxLength = lisLength[i];
}
}
return maxLength;
}

public static void main(String[] args) {
int[] array = { 12, 18, 7, 34, 30, 28, 90, 88 };
System.out.println("Length of Longest Increasing Subsequence: " + longestIncreasingSubsequence(array));
}
}
```

## Order of the Algorithm

Time Complexity is O(n^2)
Space Complexity is O(n)