给定一个序列A及它的长度n(长度小于等于500),请返回LIS的长度。
测试样例:
[1,4,2,5,3],5
返回 3
# -*- coding:utf-8 -*-
class LongestIncreasingSubsequence:
def getLIS(self, A, n):
dp = [1 for i in range(n)]
for i in range(n):
maxtemp = 0
for j in range(i):
if A[j] < A[i] and dp[j] > maxtemp:
maxtemp = dp[j]
dp[i] = maxtemp + 1
return max(dp)
以上是这个经典问题的解法。在百度一搜 LIS(最长递增子序列) 或者 LCS(最长公共子序列) 通篇都在讲什么解法最优,解的过程如何,就是没有人解释这个算法可以解决现实中的什么问题,在工作中解决什么需求,动不动就在谈思想,如果你所学的算法、技术不是为了业务服务,那学习这些东西还有什么意义?
话说回来,有木有大佬能解答一下小弟的疑问