python动态规划——最大递增序列

问题：

最长上升子序列（LIS）问题：
  给定长度为n的序列a，从a中抽取出一个子序列，
  这个子序列需要单调递增。
  问最长的上升子序列（LIS）的长度。
  e.g. 1,5,3,4,6,9,7,8的LIS为1,3,4,6,7,8，长度为6。

def func(l):
  '''
  type: l: list
  rtype: result: int
  '''

  #第一步创建保存右边比左边大的初始值，每个值的初始值都为1
  dp = [1]*len(l)

  for i in range(len(l)):
    for j in range(i):
      if l[i] > l[j]:
        #相当于选择排序，轮到该值的时候和前面的值进行依次比较，如果比前值大，dp列表中就在前值的基础上加1
        dp[i] = dp[j]+1

  print(max(dp))

问题2：

连续最长上升子序列（LIS）问题：
  给定长度为n的序列a，从a中抽取出一个子序列，这个子序列需要单调递增。
  问最长的连续上升子序列（LIS）的长度。
  e.g. 1,5,3,4,6,9,7,8的LIS为3,4,6,9,长度为4。

def func2(l):
  '''
  type: l: list
  rtype: result: int
  '''

  #第一步创建保存右边比左边大的初始值，每个值的初始值都为1
  dp = [1]*len(l)

  for i in range(1,len(l)):
    if l[i] > l[i-1]:
      dp[i] = dp[i-1]+1
  
  print(max(dp))

执行主程序：

if __name__ == '__main__':

  l = [1,5,3,4,6,9,7,8]
  func(l)
  func2(l)

运行结果：

6
4