曲健磊的个人博客
2019-06-10 16:08
采纳率: 83.3%
浏览 344

最长递增子序列问题可以在实际的工作中解决什么样的需求?

给定一个序列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(最长公共子序列) 通篇都在讲什么解法最优,解的过程如何,就是没有人解释这个算法可以解决现实中的什么问题,在工作中解决什么需求,动不动就在谈思想,如果你所学的算法、技术不是为了业务服务,那学习这些东西还有什么意义?



话说回来,有木有大佬能解答一下小弟的疑问

2条回答 默认 最新

相关推荐 更多相似问题