Longest Increasing Subsequence (最长递增子序列)

记录学习内容。看网路上大大们的文章和影片，做些纪录。
还不了解，内容可能有错误。

Longest Increasing Subsequence (最长递增子序列)

这个问题就是
如果有一个数列是

1 , 2 , 3 , 4, 5 , 6, 7

那这个数列的Longest Increasing Subsequence 就是

1 , 2 , 3 , 4, 5 , 6, 7
是7个

如果一个数列是

1 , 2 , 3 , 4, 5 , 6, 7,7,7

那这个数列的Longest Increasing Subsequence 就是

1 , 2 , 3 , 4, 5 , 6, 7
还是7个，因为是Increasing (递增)

如果是求Longest Non-Decreasing Subsequence

那就是

1 , 2 , 3 , 4, 5 , 6, 7,7,7
是9个 ，因为Non-Decreasing(不减少)

有很多种解法，先从感觉比较懂得开始看:

１　Dynamic Programming (动态规划)解法:

Find The Longest Increasing Subsequence - Dynamic Programming Fundamentals
https://www.youtube.com/watch?v=fV-TF4OvZpk&ab_channel=BackToBackSWE

教学里的例子

1、 3 、 4、 5、 2、 2、 2、 2
找这个数列的Longest Non-Decreasing Subsequence

先多准备一个阵列 ，纪录东西 。
1  3   4   5   造着顺序 ，所以1 2 3 4 代表这4个数字的Longest Non-Decreasing Subsequence 。

到数列里的2 的时候 ， 因为小於3 ，所以只接1  ，Longest Non-Decreasing Subsequence 会是 1+1 = 2 。

剩下 数列里的2 就会3 4  5 。

最後多准备的这个阵列 里面，数字最大的那个数 。
就代表这个数列 ，  最长 Non-Decreasing 的 数列 长度 。

来看程序:
300. Longest Increasing Subsequence
https://leetcode.com/problems/longest-increasing-subsequence/solution/

一

第一层回圈 ， 就是 走访数列
第二层回圈 ， 就是 i 索引之前的数字
像是现在走到 [2,3,4,5] 里的 4  ， i是 2索引 。J 是 0索引 、1索引 。
4 会先跟 2 比大小 ，4比较大 ， 所以
Math.nax(4当前LIS , 2的LIS ) 。 决定要不要更新4 的LIS 。

最後结果--- > dp[]里 的每个数字 代表 那个数字的Longest Increasing Subsequence ，
所以 dp[]里最大的那个数字 ，会是答案

这边的写法是 ，每一个数字算出Longest Increasing Subsequence 後 ，就去更新最大值 。
maxans 最後就会是 dp[]里最大的那个数字 。 (最大数字可能有很多一样的，因为Longest Increasing Subsequence 可能有很多个)

二

if (nums[i] > nums[j]) {
    maxval = Math.max(maxval, dp[j]);
}

改成

if (nums[i] >= nums[j]) {
    maxval = Math.max(maxval, dp[j]);
}

就变成Longest Non-Decreasing Subsequence 了

时间复杂度 :

time -- > 因为1+2+3+….n-1 ，会有 n * n 出现 (两层回圈)
space -- > 因为要多准备一个阵列 n size

2 Dynamic Programming with Binary Search

input: [0, 8, 4, 12, 2]
dp: [0]
dp: [0, 8]
dp: [0, 4]
dp: [0, 4, 12]
dp: [0 , 2, 12]

这个方法也是走访每一个数字 ，
先准备一个阵列dp 。
一开始是0 ，就放0 。
接着 Binary Search  8  ，因为dp里只有0 ，8大於0 ，所以继续放8 。

接着 Binary Search   4 ，因为dp介於0-8之间，所以 不是变成0 4 8 ，而是变成0 4 ，因为4<8 不能0 4 8 ，
所以只能取代 8。

接着 Binary Search   12 ，因为12 最大 ， 所以放到最後面 0 4 12 。
接着 Binary Search   2 ，2介於0-4 ，取代4 ，变成0、2、12 。

所以最後的阵列长度 ，就是答案 。
不懂 ，总之先知道方法 。

leetcode范例里的解答看不懂，看这篇文章:

[LeetCode] 300. Longest Increasing Subsequence 最长递增子序列
https://www.cnblogs.com/grandyang/p/4938187.html

解法2 :

最小放dp[0] ，最大放dp的最後面 。
其他的用Binary Search ，找到 第一个 不小於(大於等於) 这个元素的index，
盖掉他

像是

input: [0, 8, 4, 12, 2]

dp: [0]

dp: [0, 8]:

    第一次
    left =0 ，right = 2
    mid = 0 +  2/2  = 1
    if ( 8 < 4) left = mid+ 1
    else right = mid       //( right = 1)

    第二次
    left =0 ，right = 1
    mid = 0 +  1/2  = 0
    if ( 0< 4) left = mid+ 1  // left = 1
    else right = mid  

    之後
    Ends [1 ]  = 4

所以变成[0,4]

复杂度

时间复杂度:

因为 回圈 长度 n ，每一轮Binary Search 都logn 。
时间复杂度 n * logn

3 Brute Force

觉得递回的方法最难懂。
平常的递回都是5 4 3 2 1 ，从n到1 。
但是这个演算法的递回是从0 到 n ，12345。

Nums 是 数字阵列 。
Curpos  指的是current position ，现在在哪个阵列索引 。
Prev 指的是 上一个要比较的值(value) 。

如果数列是 1 2 3 4 5

现在在2 ， 2 可以选择 ，2可以不选择 。
选择-- >  1 (长度+1)  + 下一个递回( 比较的数字从1移动2 , current position+1)
不选择 --- >下一个递回( 比较的数字还是1, current position+1)

教学来源:
花花酱 LeetCode 300. Longest Increasing Subsequence (Dynamic Programming O(n^2)) - 刷题找工作 EP48
https://www.youtube.com/watch?v=7DKFpWnaxLI&t=974s&ab_channel=HuaHua