问题描述：
给定一个数组str=[5, 3, 4, 8, 6, 7,9]，求出其最长递增子串：LongestIncreaseSub=[3,4,6,7,9]
解决思路：
解决最长子序列（Longest Increase Subset, LIS）问题，使用动态规划（Dynamic Programming，DP），之前说到动态规划的规划（Programming）是表格的意思，是对递归的一种优化，递归是不管需不需要都进行重新计算，其计算复杂度极高，动态规划用表格（数组）来存储其之前的状态，当进行下一步计算的时候直接调用不需要重新计算。那么问题来了，动态规划需要确定两个点：状态、状态转移方式[1]。在这里从另一个角度说一下动态规划：
已知问题规模为n的已知条件Y，求解一个未知解X。（我们用Yn表示“问题规模为n的已知条件”）
此时，如果把问题规模降到0，即已知Y0，可以得到Y0->X.
如果从Y0添加一个元素，得到Y1的变化过程。即Y0->Y1; 进而有Y1->Y2; Y2->Y3; …… ; Yi->Yi+1. 这就是严格的归纳推理，也就是数学归纳法；
对于Yi+1，只需要它的上一个状态Yi即可完成整个推理过程（而不需要更前序的状态）。我们将这一模型称为马尔科夫链(自然语言处理中经常使用)。对应的推理过程叫做“贪心法”。
然而，Yi与Yi+1往往不是互为充要条件，随着i的增加，有价值的前提信息越来越少，我们无法仅仅通过上一个状态得到下一个状态，因此可以采用如下方案：{Y1->Y2}; {Y1, Y2->Y3}; {Y1,Y2,Y3->Y4};……; {Y1,Y2,...,Yi}->Yi+1. 对于Yi+1需要前面的所有前序状态才能完成推理过程, 高阶马尔科夫链。也就是DP的另一个解释。
借用文献[2]中一个形象的图就是:
文献[3]中说动态规划就是一个基于有模型的强化学习方法。
回归到本文的问题，首先应当记录在有1，2，3，m,...n 个元素时各自的LIS；
然后在建立第m个元素时LIS时，需要考虑当前缀为1，2...,m时的递增长度，取其中最长的。
例如对于这个序列str=[5, 3, 4, 8, 6, 7,9]，当考虑元素6的时候，其最长子序列为以4结尾的LIS，而4的LIS是以3结尾的LIS，如图所示：
所以其状态转移公式为：if(str[m]>str[preIndex]): LIS[m]=max{ LIS[preIndex]+1 }
此处需要使用两层for循环进行遍历，第一次表示当有index个数据时的最长子串，第二次表示当前缀为preIndex是的长度，然后判断是否更新。
python代码：
import copy
# 最长递增子串
str=[5, 3, 4, 8, 6, 7,9]
def find(str):
long=1
status = []
sub=[]
for index in range(len(str)): # 从第0个元素开始建立
status.append(1)
pre=0
for preIndex in range(index): # 从前面（第0个）元素中开始更新
if(str[preIndex]<=str[index] and status[preIndex]+1>status[index]):
# 如果当前元素小于元素，且更新后长度更长
status[index]=status[preIndex]+1
pre=preIndex
# 记录每一种状态下的子串
# print("pre",pre)# 记录的是上一个合适的子串的位置
if(status[index]>long):
long=status[index]
if(long==1):
sub.append([str[index]])
else:
new=copy.copy(sub[pre])
new.append(str[index])
sub.append(new)
# print(new)
print(str)
print(long)
print(status)
print(sub)
if __name__=="__main__":
find(str)运行结果为：
其中，最后一行为在不同数据长度下的LIS记录。使用pre变量记录最长递增子串的前缀，当记录清所有前缀后，即可记录并打印出所有的子串。
参考文献：
[1] 0-1背包问题：动态规划 python 空间优化 https://blog.csdn.net/linweieran/article/details/100585052
[2] 六大算法之三：动态规划 https://blog.csdn.net/zw6161080123/article/details/80639932
[3] 动态规划(Dynamic Programming):基于有模型的强化学习方法 https://www.jianshu.com/p/f63d674b7688