Longest-Increasing-Subsequence

¶开始 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

基于Recursion，可以用 DP 节省时间，大概因为自己基础不太好的原因，听现在这个老师的讲课听得我很迷茫，于是准备重新搞一下这道题。

对于Dynamic Programming：课上总结了以下的general steps:

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

在这一题中，书上提供的思路为把input 看作是一个DAG (directed acyclic graph) $E$，每个node 是一个数字，对于这个DAG 上的node， 编上序号为 $a_{i}$ 和 $a_{j}$ ，edge 的创建条件如下（引用原文）：

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)$

即：

# Dynamic programming Python implementation
# of LIS problem
 
# lis returns length of the longest
# increasing subsequence in arr of size n
def lis(arr):
    n = len(arr)
 
    # Declare the list (array) for LIS and
    # initialize LIS values for all indexes
    lis = [1]*n
 
    # Compute optimized LIS values in bottom up manner
    for i in range (1 , n):
        for j in range(0 , i):
            if arr[i] > arr[j] and lis[i]< lis[j] + 1 :
                lis[i] = lis[j]+1
 
    # Initialize maximum to 0 to get
    # the maximum of all LIS
    maximum = 0
 
    # Pick maximum of all LIS values
    for i in range(n):
        maximum = max(maximum , lis[i])
 
    return maximum
# end of lis function
 
# Driver program to test above function
arr = [10, 22, 9, 33, 21, 50, 41, 60]
print "Length of lis is", lis(arr)
# This code is contributed by Nikhil Kumar Singh

来源：GeeksForGeeks

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

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

¶运行时间 Run-time

$O(n^2)$

因为DP 是基于 recursion 上更改的（Iteration 版本每次iterate整个arr[0:i] for i< len(arr)。 DP 的优势在于 把每个node 的LIS result 都存到了一个array中，这样不需要重复计算已经计算过的sub-problem。

¶反思 Introspection

学习算法，光认真听课收获不会很大，结合书本，网络，油管对算法进行进一步的实现会有更大帮助