### Introduction

In this article I will describe two **dynamic programming** algorithms solving LIS problem and **STL functions** `lower_bound()`

and `upper_bound()`

.

### Description

Given an unsorted array of integers, find the length of longest increasing subsequence.

Example:

Input: $[10,9,2,5,3,7,101,18]$

Output: 4

Explanation: The longest increasing subsequence is $[2,3,7,101]$, therefore the length is $4$.

### $O(n^2)$ Dynamic Programming Solution

Here is a trivial description that `dp[i]`

means the length of longest increasing subsequence **with $i^{th}$ element.** Also, we can find easily that the value of `dp[i]`

can be determined by all increasing subsequence with $j < i$ that **maintain increasing property** with $i^{th}$ value. Mathematically, `dp[i]`

is determined by all the value `dp[j]`

with $j < i$ and $nums[i] > nums[j]$ which `nums`

is the input vector. So the state transition equation is

dp[i] = max(dp[j]) + 1 with j < i, nums[j] < nums[i]

This method need two iterations so it’s a $O(n^2)$ algorithm.

1 | class Solution { |

### $O(nlgn)$ Dynamic Programming Solution

Comparing all optimal subsequences with the same length, the one **with least last number** will confirm that when a new number is added in, the new subsequence will still optimal. For example, for subsequence $[1,3,5,2,7,4,5]$, we have two subsequences length $4$:

Then we add $6$ into the sequence, the first subsequence is still $[1,3,5,7]$ when the second one becomes $[1,2,4,5,6]$.

But how to guarantee that the subsequence has the least last number? We can do so by replacing the number **just larger than the new number** with the new number. It’s because the replacement won’t change the length of the subsequence but will decrease the number value generally.

There is a very great property that the increasing subsequences are ‘increasing’, which means that given a increasing subsequence and a new number, we can find the **correct position** of the new number in the subsequence in only $O(lgn)$ time. We can generate a new largest increasing subsequence including the new number by **adding the new number** if it’s larger than all numbers in the subsequence and do replacing if not. The whole time complexity will be $O(nlgn)$.

1 | class Solution { |

`lower_bound`

and `upper_bound`

in STL

We can mention that I use `lower_bound`

function in the previous code. It’s a binary search function in STL. Both it ans `upper_bound`

use binary search and return a position of a vector. The difference is that `lower_bound`

return the position of the first number larger than **or equals to** the target and `upper_bound`

return the position of the first number **strictly** larger than the target. There are three parameters in both functions. The first parameter is a Iterator refers to the search begin position, the second parameter is a Iterator refers to the end position and the third parameter is target number. Here is the source code of `lower_bound`

.

1 | template <class ForwardIterator, class T> |

What should be mentioned is that **the begin position will be included but the end position won’t be included.** The function uses **binary search**, so the time complexity is $O(lgn)$ where $n$ is the size between two pointers.