最长递增序列

1.1 最长递增子序列

从一个给定的序列中找出一个最长的序列，该序列从小到大进行排序。比如：一个给定的序列如下所示：0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15
那么，它的最长子序列就是：0, 2, 6, 9, 11, 15

一种思路如下图，首先组合出所有的可能序列，然后从最长的序列开始，逐步减小为1，找最大的递增子序列，这种方法的时间复杂度较高，如下所示：

另一种思路就是动态规划：比如针对序列：{3,2,6,4,5,1}，存储在数组D中，设L[i]存储以第i个元素结尾是的最大序列，则有:
L[0] = [3] L[1] = [2] L[2] = [2,6] L[3] = [2,4] L[4] = [2,4,5] L[5] = [1]
使用动态规划的思想，主要是考虑L[i]目前已经求得的L[0]至L[i-1]的基础上进行，判断条件是：

L[i] = max(L[j] | j<i ,D[j]< D[i]) +"D[i]" 

代码如下：

class Solution:
    def lengthOfLIS(self, nums):
        if len(nums)==0:
            return 0

        L = [[] for i in range(len(nums))]

        L[0] = [nums[0]]

        for i in range(1, len(nums)):
            for j in range(i):
                if nums[i] > nums[j] and len(L[i]) < (len(L[j])+1):
                    L[i] = L[j][:]
            L[i].append(nums[i])

        max_len = 0
        for i in L:
            if len(i)>max_len:
                max_len = len(i)
        return max_len

通过上面的结果可以发现，L[2]不是[3,6]，而是[2,6]，这是因为代码中j遍历的时候，先得到[3,6],之后被[2,6]覆盖了。

以上代码虽然通过了leetcode-300-最长上升子序列所有的测试用例，但是会超出时间限制。原因主要是，L中保存了具体的以i结尾的最长序列，而题目要求的是最大长度，因此可以修改如下。

修改：使用dp保存 以第i个元素结尾的最大长度 ，其余部分不变，如下所示：

class Solution:
    def lengthOfLIS(self, nums):
        if len(nums)==0:
            return 0

        dp = [1 for i in range(len(nums))]
        for i in range(1, len(nums)):
            for j in range(i):
                if nums[i] > nums[j]and dp[i] < dp[j] + 1:
                    dp[i] = dp[j] + 1

        return max(dp)

进阶：保存具体的最长子序列

class Solution:
    def lengthOfLIS(self, nums):
        if len(nums)==0:
            return 0

        dp = [1 for i in range(len(nums))]
        L = [[] for i in range(len(nums))]
        L[0] = [nums[0]]

        for i in range(1, len(nums)):
            for j in range(i):
                if nums[i] > nums[j] and dp[i] < dp[j] + 1:
                    dp[i] = dp[j] + 1
                    L[i] = L[j][:]  # 更新L[i]。
            L[i].append(nums[i])  # 注意，这里需要在遍历里层循环结束之后，将第i个元素的值插入到最后。
        print(L)
        return max(dp)

输入：[2,5,3,7]
输出: [[2], [2, 5], [2, 3], [2, 5, 7]]

问题：结果中输出的最长序列为[2,5,7]，而[2,3,7]也是最长序列。通过分析发现，当i等于3时（也就是i指向7），此时当j指向5时，由于5<7，而此时的dp[3]=2,dp[1]=2,因此更新之后dp[3]=3,而当j指向3的时候，由于dp[j]+1=dp[i]，因此，不进行更新，从而导致L中只保存了[2,5,7]，所以关键问题在于当dp[j]+1=dp[i]时，如何保存多个最大序列。

进阶：输出所有最长序列

class Solution:
    def lengthOfLIS(self, nums):
        if len(nums)==0:
            return 0

        dp = [1 for i in range(len(nums))]

        for i in range(1, len(nums)):
            for j in range(i):
                if nums[i] > nums[j] and dp[i] < dp[j] + 1:
                    dp[i] = dp[j] + 1
        print(dp)       # [1,1,2,2,2,3]

        max_len = max(dp)
        L = [[] for i in range(max_len)]       # [[2,1], [5,4,3], [6]]
        # 保存dp中对应长度的数值。

        for i in range(len(dp)):
            L[dp[i]-1].append(nums[i])

        print(L)
        result = []
        def helper(i, res):
            if len(res) == max_len:
                result.append(res.copy())
                return
            for k in range(len(L[i])):
                res.append(L[i][k])
                helper(i+1, res)
                res.pop()
        helper(0, [])
        return dp, max(dp),result

思路：比如针对输入[2,1,5,4,3,6],对应的dp输出为[1,1,2,2,2,3]。由于dp中保存的是以该位置为结尾时的最大长度。因此可以首先输出dp中长度为3的位置的元素，然后输出长度为2的元素，然后在输出长度为1的元素，之后逆序就可以得到对应的最长序列。

但是从dp中可以看出，长度为1序列有2个，长度为2的序列就有2*3为6个，长度为3的序列就为2*3*1为6个，要想输出所有的序列，那么需要进行组合。

首先，根据dp中不同值，将对应nums值存储在L中，可以得到[[2, 1], [5, 4, 3], [6]]，含义就是[2,1]表示以2或者1结尾的元素长度为1，[5,4,3]就是以5或4或3结尾的最大序列长度为2，以此类推。

接着，每次从L中每一项取一个元素，然后组合在一起成最大序列，此时就是一种最大序列的组合。考虑使用深度递归方法，输出所有组合如下：[[2, 5, 6], [2, 4, 6], [2, 3, 6], [1, 5, 6], [1, 4, 6], [1, 3, 6]]，这就是所有的组合。 --2020-09-21.【S 后续可以继续整理，添加图片和规范说明，整理到blog中】

【注意】可以看一下《算法分析与设计》中的相关代码，上面的代码应该还存在一定的问题，觉得最好是求最优值（最长公共子序列长度），之后求最优解（最长公共子序列），这样比较符合动态规划的解题过程。

1.2 最长连续递增序列

思路：如果nums[i]大于nums[i-1],此时就max_i+1,max_i表示以i结尾的最大连续序列长度。然后比较max_i与max_len，将最大的长度保存到max_len中。如果nums[i]小于nums[i-1]，此时表示连续递增断开，需要重新开始，因此max_i=1.

class Solution:
    def findLengthOfLCIS(self, nums):
        if len(nums)==0:
            return 0

        n = len(nums)
        max_len = 1

        for i in range(n):
            if i == 0:
                max_i = 1
            else:
                if nums[i] > nums[i - 1]:
                    max_i += 1
                else:
                    max_i = 1   
            max_len = max(max_len, max_i)
        return max_len

进阶：存储最长的连续递增子序列。L保存所有的连续递增序列，tmp保存当前的连续递增序列。由于当nums[i]小于nums[i-1]的时候，相当于重新开始，因此此时将tmp结果保存到L中。

class Solution:
    def findLengthOfLCIS(self, nums):
        if len(nums)==0:
            return 0
        n = len(nums)
        max_len = 1
        L = []
        tmp = []
        for i in range(n):
            if i == 0:
                max_i = 1
                tmp.append(nums[i])
            else:
                if nums[i] > nums[i - 1]:
                    max_i += 1
                else:
                    L.append(tmp)
                    tmp = []
                    max_i = 1
                tmp.append(nums[i])
            max_len = max(max_len, max_i)
        L.append(tmp)
        return max_len, L
# s = Solution()
# nums = [2,2,2,2,2]
# print(s.findLengthOfLCIS(nums))