LintCode 76 [Longest Increasing Subsequence]

原题

给定一个整数序列，找到最长上升子序列（LIS），返回LIS的长度。

给出[5,4,1,2,3]，这个LIS是[1,2,3]，返回 3
给出[4,2,4,5,3,7]，这个LIS是[4,4,5,7]，返回 4

最长上升子序列问题是在一个无序的给定序列中找到一个尽可能长的由低到高排列的子序列，这种子序列不一定是连续的或者唯一的。

解题思路

• 序列型动态规划 - Sequence DP
• 判定条件：序列非集合，求最长
• cache[i]表示以i结尾的最长子序列的长度
• 每次遍历0 ~ i-1如果存在nums[x] < nums[i]并且cache[x] + 1 > cache[i]则更新
• for循环中维护一个res，即最大值

完整代码

class Solution:
    """
    @param nums: The integer array
    @return: The length of LIS (longest increasing subsequence)
    """
    def longestIncreasingSubsequence(self, nums):
        cache = [1 for i in range(len(nums))]
        res = 0

        for i in range(1, len(nums)):
            for j in range(i):
                if nums[j] <= nums[i]:
                    if cache[j] + 1 > cache[i]:
                        cache[i] = cache[j] + 1
            if cache[i] > res:
                res = cache[i]
            
        return res