3、递增子序列

300. 最长递增子序列——子序列可以是不连续

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例 2：

输入：nums = [0,1,0,3,2,3]
输出：4

示例 3：

输入：nums = [7,7,7,7,7,7,7]
输出：1

思路

什么是递增子序列，就是后一个数大于前面的一个数，但是可以不连续。

动规五部曲：

• 确定dp数组含义：dp[i]是指以i结尾的字符串中最长的递增子序列，这里最长的子序列不一定为最后一个字符结尾的
• 递推公式：dp[i] = max(dp[i], dp[j]+1)
• 初始化：每个字符串都是一个长度为一的递增子序列
• 遍历顺序：从左到右

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        if n <= 1:
            return n
        dp = [1] * n
        for i in range(1, n):
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[j] + 1, dp[i])
        # print(dp)
        return max(dp)

674. 最长连续递增序列——最长联系递增子序列

给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。

连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。

示例 1：

输入：nums = [1,3,5,4,7]
输出：3
解释：最长连续递增序列是 [1,3,5], 长度为3。
尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为 5 和 7 在原数组里被 4 隔开。 

示例 2：

输入：nums = [2,2,2,2,2]
输出：1
解释：最长连续递增序列是 [2], 长度为1。

思路：

和上题一致，还要比上题简单

class Solution:
    def findLengthOfLCIS(self, nums: List[int]) -> int:

        n = len(nums)
        if n <= 1:
            return n
        dp = [1] * n
        for i in range(1, n):
            if nums[i] > nums[i - 1]:
                dp[i] = max(dp[i], dp[i - 1] + 1)
        print(dp)
        return max(dp)

673. 最长递增子序列的个数——最长递增子序列个数

给定一个未排序的整数数组 nums ， 返回最长递增子序列的个数 。

注意 这个数列必须是 严格 递增的。

示例 1:

输入: [1,3,5,4,7]
输出: 2
解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。

示例 2:

输入: [2,2,2,2,2]
输出: 5
解释: 最长递增子序列的长度是1，并且存在5个子序列的长度为1，因此输出5。

思路：

这题和第一题看起来相似但是差别很大。

这题因为要求最长递增子序列个数，所以也需要求最长子序列的长度。然后再统计个数(最长子序列的个数)

如果我们直接定义dp[i]为最长子序列个数为dp[i],我们找不到递推公式。

所以我们需要定义两个dp数组，

第一个dp是最长子序列长度，第二个是最长子序列个数，个数根据最长子序列长度来算出来

class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        if n <= 1:
            return n
        dp = [1] * n
        count = [1] * n
    
        for i in range(1, n):
            for j in range(i):
                if nums[i] > nums[j]:
                    if dp[j] + 1 > dp[i]:
                        dp[i] = dp[j] + 1
                        count[i] = count[j]
                    elif dp[j] + 1 == dp[i]:
                        count[i] += count[j]
            
        max_length = max(dp)
        result = 0
        for i in range(n):
            if dp[i] ==max_length:
                result += count[i]
        return result

334. 递增的三元子序列——递增三元子序列

给你一个整数数组 nums ，判断这个数组中是否存在长度为 3 的递增子序列。

如果存在这样的三元组下标 (i, j, k) 且满足 i < j < k ，使得 nums[i] < nums[j] < nums[k] ，返回 true ；否则，返回 false 。

示例 1：

输入：nums = [1,2,3,4,5]
输出：true
解释：任何 i < j < k 的三元组都满足题意

示例 2：

输入：nums = [5,4,3,2,1]
输出：false
解释：不存在满足题意的三元组

示例 3：

输入：nums = [2,1,5,0,4,6]
输出：true
解释：三元组 (3, 4, 5) 满足题意，因为 nums[3] == 0 < nums[4] == 4 < nums[5] == 6

一开始我想用dp数组的方式，但是超时了

class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        if len(set(nums)) < 3:
            return False
        n = len(nums)
        if n < 3:
            return False
        dp = [1] * n
        for i in range(1, n):
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[j]+1, dp[i])
                    if dp[i] == 3:
                        return True
        return False

正确思路应该是贪心

class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        if len(set(nums)) < 3:
            return False
        n = len(nums)
        if n < 3:
            return False

        first = float('inf')
        second = float('inf')

        for three in nums:
            if three > second:
                return True
            elif three <= first:
                first = three
            else:
                second = three
        return False