## 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] = 1

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

lisLength[1] = lisLength[0] + 1 = 2

lisLength[] : [1, 2, 0, 0, 0, 0, 0, 0]

i = 2: lisLength[2] = 1

j = 0: input[0] = 12 > input[2] = 7

j = 1: input[1] = 18 > input[2] = 7

lisLength[] : [1, 2, 1, 0, 0, 0, 0, 0]

i = 3: lisLength[3] = 1

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

lisLength[3] = lisLength[0] + 1 = 2

j = 1: input[1] = 18 < input[3] = 34, also lisLength[3] = 2 < lisLength[1] + 1 = 3, so we update:

lisLength[3] = lisLength[1] + 1 = 3

j = 2: input[2] = 7 < input[3] = 34, but lisLength[3] = 3 > lisLength[2] + 1 = 2, so lisLength is not updated.

lisLength[] : [1, 2, 1, 3, 0, 0, 0, 0]

i = 4: lisLength[4] = 1

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

lisLength[4] = lisLength[0] + 1 = 2

j = 1: input[1] = 18 < input[4] = 30, also lisLength[4] = 2 < lisLength[1] + 1 = 3, so we update:

lisLength[4] = lisLength[1] + 1 = 3

j = 2: input[2] = 7 < input[4] = 30, but lisLength[4] = 3 > lisLength[2] + 1 = 2, so lisLength is not updated.

j = 3: input[3] = 34 > input[4] = 30

lisLength[] : [1, 2, 1, 3, 3, 0, 0, 0]

i = 5: lisLength[5] = 1

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

lisLength[5] = lisLength[0] + 1 = 2

j = 1: input[1] = 18 < input[5] = 28, also lisLength[5] = 2 < lisLength[1] + 1 = 3, so we update:

lisLength[5] = lisLength[1] + 1 = 3

j = 2: input[2] = 7 < input[5] = 28, but lisLength[5] = 3 > lisLength[2] + 1, so lisLength is not updated.

j = 3: input[3] = 34 > input[5] = 28

j = 4: input[4] = 30 > input[5] = 28

lisLength[] : [1, 2, 1, 3, 3, 3, 0, 0]

i = 6: lisLength[6] = 1

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

lisLength[6] = lisLength[0] + 1 = 2

j = 1: input[1] = 18 < input[6] = 90, also lisLength[6] = 2 < lisLength[1] + 1 = 3, so we update:

lisLength[6] = lisLength[1] + 1 = 3

j = 2: input[2] = 7 < input[6] = 90, but lisLength[6] = 3 > lisLength[2] + 1, so lisLength is not updated.

j = 3: input[3] = 34 < input[6] = 90, also lisLength[6] = 3 < lisLength[3] + 1 = 4, so we update:

lisLength[6] = lisLength[3] + 1 = 4

j = 4: input[4] = 30 < input[6] = 90, but lisLength[6] = 4 = lisLength[4] + 1, so lisLength is not updated.

j = 5: input[5] = 28 < input[6] = 90, but lisLength[6] = 4 = lisLength[5] + 1, so lisLength is not updated.

lisLength[] : [1, 2, 1, 3, 3, 3, 4, 0]

i = 7: lisLength[7] = 1

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

lisLength[7] = lisLength[0] + 1 = 2

j = 1: input[1] = 18 < input[7] = 88, also lisLength[7] = 1 < lisLength[1] + 1 = 3, so we update:

lisLength[7] = lisLength[1] + 1 = 3

j = 2: input[2] = 7 < input[7] = 88, but lisLength[7] = 3 > lisLength[2] + 1, so lisLength is not updated.

j = 3: input[3] = 34 < input[7] = 88, also lisLength[7] = 3 < lisLength[3] + 1 = 4, so we update:

lisLength[7] = lisLength[3] + 1 = 4

j = 4: input[4] = 30 < input[7] = 88, but lisLength[7] = 4 = lisLength[4] + 1, so lisLength is not updated.

j = 5: input[5] = 28 < input[7] = 88, but lisLength[7] = 4 = lisLength[5] + 1, so lisLength is not updated.

j = 6: input[6] = 90 > input[7] = 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