最长上升子序列

最长子序列

最近力扣推送了最长子序列的解法，发现自己好久没做算法题了。决定尝试一下。

经过一番思考，我认为此题有以下特点：

1. 每一个新数字，需要和现有子序列的最大值进行比较，只有大于当前子序列的最大值才能加入该序列。
2. 当一个新数字大于多个子序列的最大值时，加入容量最大的那个子序列。
3. 当一个新数字比所有子序列的最大值都来得小的时候，新建一个子序列。

因此，我最一开始的代码是这样：

class Solution(object):

    @staticmethod
    @pysnooper.snoop()
    def lengthOfLIS(nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        array_lis = []
        for num in nums:
            if len(array_lis) == 0:
                array_lis.append([num, 1])
            else:
                temp_index_array = []
                max_index = -1
                max_len = 0
                for index, lis in enumerate(array_lis):
                    if array_lis[index][0] < num:
                        if array_lis[index][1] > max_len:
                            max_len = array_lis[index][1]
                            max_index = index
                if max_index >= 0:
                    array_lis[max_index][0] = num
                    array_lis[max_index][1] += 1
                else:
                    array_lis.append([num, 1])

        max_len = 0
        for lis in array_lis:
            if lis[1] > max_len:
                max_len = lis[1]

        return max_len

很快，遇到了一个问题，如下的list：

list_in = [10, 9, 2, 5, 3, 4]

可以看出，最长上升子序列应该是2, 3, 4，然而，根据我上面的算法，扫描到2, 5之后，3, 4会自成序列，因此上述的算法是有问题的。需要保存之前列表的信息。

因此，我将一个数加入一个序列的时候，选择新建一个序列而不是更改原序列的信息。新的代码如下：

class Solution(object):

    @staticmethod
    @pysnooper.snoop()
    def lengthOfLIS(nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        array_lis = []
        for num in nums:
            if len(array_lis) == 0:
                array_lis.append([num, 1])
            else:
                temp_index_array = []
                max_index = -1
                max_len = 0
                for index, lis in enumerate(array_lis):
                    if array_lis[index][0] < num:
                        if array_lis[index][1] > max_len:
                            max_len = array_lis[index][1]
                            max_index = index
                if max_index >= 0:
                    array_lis.append([num, array_lis[max_index][1]+1])
                else:
                    array_lis.append([num, 1])

        max_len = 0
        for lis in array_lis:
            if lis[1] > max_len:
                max_len = lis[1]

        return max_len

这样成功通过了测试。

image.png

可以看到，其实还是有很多上升空间的。