# 开始 Starting

Longest Increasing Subsequence

Algorithm by Sanjoy Dasgupta p. 171

https://leetcode.com/problems/longest-increasing-subsequence/

# 题目 Question

Given an integer array nums, return the length of the longest strictly increasing subsequence.

A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].

# 想法 Thinking

1. Break problem into smaller subproblem
2. Solve smaller subproblems first (bottom-up)
3. Use information from smaller problem to solve a large subproblem

Establish a node i for each element ai , and add directed edges (i, j) whenever it is possible for ai and aj to be consecutive elements in an increasing subsequence, that is, whenever i < j and ai < aj

# 算法 Algorithm

for j = 1,2,3,…,n:

​ $L(j) = 1+max{L(i): (i,j) \in E}$

return $max_{j}L(j)$

node 是否存在 由：if arr[i] > arr[j] 实现

max function是 由: lis[i]< lis[j] + 1  实现

# 运行时间 Run-time

$O(n^2)$