The task is to find the length of the longest subsequence in a given array of integers such that all elements of the subsequence are sorted in ascending order. For example, the length of the longest increasing subsequence(LIS) for **{15, 27, 14, 38, 26, 55, 46, 65, 85}** is **6** and the longest increasing subsequence is **{15, 27, 38, 55, 65, 85}**. Again for **{3, 4, -1, 0, 6, 2, 3}** length of LIS is **4** and the subsequence is **{-1, 0, 2, 3}**. We'll use dynamic programming to solve this problem.

Let's take the second example: `Item = {3, 4, -1, 0, 6, 2, 3}`

. We'll start by taking the an array **dp** of the same size of our sequence. **dp[i]** represents the length of the LIS if we include the **i**th item of our original sequence. At the very beginning we know that for each and every item at least the longest increasing subsequence is of length **1**. That is by considering the single element itself. So we'll initialize the **dp** array with **1**. We'll have two variables **i** and **j**. Initially **i** will be **1** and **j** will be **0**. Our array will look like:

```
3 4 -1 0 6 2 3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
+-------+-----+-----+-----+-----+-----+-----+-----+
j i
```

The number above the array represents the corresponding element of our sequence. Our strategy will be:

```
if Item[i] > Item[j]
dp[i] := dp[j] + 1
```

That means if element at **i** is greater than element at **j**, the length of the LIS that contains element at **j**, will increase by length **1** if we include element at **i** with it. In our example, for **i** = **1** and **j** = **0**, **Item[i]** is greater than **Item[j]**. So **dp[i]** = **dp[j]** + **1**. Our array will look like:

```
3 4 -1 0 6 2 3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value | 1 | 2 | 1 | 1 | 1 | 1 | 1 |
+-------+-----+-----+-----+-----+-----+-----+-----+
j i
```

At each step, we'll increase **j** up to **i** and then reset **j** to **0** and increment **i**. For now, **j** has reached **i**, so we increment **i** to **2**.

```
3 4 -1 0 6 2 3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value | 1 | 2 | 1 | 1 | 1 | 1 | 1 |
+-------+-----+-----+-----+-----+-----+-----+-----+
j i
```

For **i** = **2**, **j** = **0**, **Item[i]** is not greater than **Item[j]**, so we do nothing and increment **j**.

```
3 4 -1 0 6 2 3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value | 1 | 2 | 1 | 1 | 1 | 1 | 1 |
+-------+-----+-----+-----+-----+-----+-----+-----+
j i
```

For **i** = **2**, **j** = **1**, **Item[i]** is not greater than **Item[j]**, so we do nothing and since **j** has reached its limit, we increment **i** and reset **j** to **0**.

```
3 4 -1 0 6 2 3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value | 1 | 2 | 1 | 1 | 1 | 1 | 1 |
+-------+-----+-----+-----+-----+-----+-----+-----+
j i
```

For **i** = **3**, **j** = **0**, **Item[i]** is not greater than **Item[j]**, so we do nothing and increment **j**.

```
3 4 -1 0 6 2 3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value | 1 | 2 | 1 | 1 | 1 | 1 | 1 |
+-------+-----+-----+-----+-----+-----+-----+-----+
j i
```

For **i** = **3**, **j** = **1**, **Item[i]** is not greater than **Item[j]**, so we do nothing and increment **j**.

```
3 4 -1 0 6 2 3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value | 1 | 2 | 1 | 1 | 1 | 1 | 1 |
+-------+-----+-----+-----+-----+-----+-----+-----+
j i
```

For **i** = **3**, **j** = **2**, **Item[i]** is greater than **Item[j]**, so **dp[i]** = **dp[j]** + **1**. After that since **j** has reached its limit, again we reset **j** to **0** and increment **i**.

```
3 4 -1 0 6 2 3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value | 1 | 2 | 1 | 2 | 1 | 1 | 1 |
+-------+-----+-----+-----+-----+-----+-----+-----+
j i
```

For **i** = **4** and **j** = **0**, **Item[i]** is greater than **Item[j]**, so **dp[i]** = **dp[j]** + **1**. After that, we increment **j**.

```
3 4 -1 0 6 2 3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value | 1 | 2 | 1 | 2 | 2 | 1 | 1 |
+-------+-----+-----+-----+-----+-----+-----+-----+
j i
```

For **i** = **4** and **j** = **1**, **Item[i]** is greater than **Item[j]**. We can also notice that **dp[i]** = **dp[j]** + **1** will provide us **3**, which means if we take the LIS for **Item[j]** and add **Item[i]** with it, we'll get a better LIS{3,4,6} than before {3,6}. So we set **dp[i]** = **dp[j]** + **1**. Then we increment **j**.

```
3 4 -1 0 6 2 3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value | 1 | 2 | 1 | 2 | 3 | 1 | 1 |
+-------+-----+-----+-----+-----+-----+-----+-----+
j i
```

For **i** = **4** and **j** = **2**, **Item[i]** is greater than **Item[j]**. But for this case, if we set **dp[i]** = **dp[j]** + **1**, we'll get **2**, which is{-1,6} not the best{3,4,6} we can do using **Item[i]**. So we discard this one. We'll add a condition to our strategy, that is:

```
if Item[i]>Item[j] and dp[i]<dp[j] + 1
dp[i] := dp[j] + 1
```

We increment **j** by **1**. Following this strategy, if we complete our **dp** array, it will look like:

```
3 4 -1 0 6 2 3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value | 1 | 2 | 1 | 2 | 3 | 3 | 4 |
+-------+-----+-----+-----+-----+-----+-----+-----+
j i
```

Now we'll iterate through this array and find out the maximum value, which will be the length of the LIS. Our pseudo-code will be:

```
Procedure LISLength(Item):
n := Item.length
dp[] := new Array(n)
for i from 0 to n
dp[i] := 1
end for
for i from 1 to n
for j from 0 to i
if Item[i]>Item[j] and dp[i]<dp[j] + 1
dp[i] := dp[j] + 1
end if
end for
end for
l := -1
for i from 0 to n
l := max(l, dp[i])
end for
Return l
```

The time complexity of this algorithm is `O(n²)`

where **n** is the length of the sequence.

To find out the original sequence, we need to iterate backwards and match it with our length. The procedure is:

```
Procedure LIS(Item, dp, maxLength):
i := Item.length
while dp[i] is not equal to maxLength
i := i - 1
end while
s = new Stack()
s.push(Item[i])
maxLength := maxLength - 1
current := Item[i]
while maxLength is not equal to 0
i := i-1
if dp[i] := maxLength and Item[i] < current
current := Item[i]
s.push(current)
maxLength := maxLength - 1
end if
end while
while s is not empty
x := s.pop
Print(s)
end while
```

The time complexity of this algorithm is: `O(n)`

.