1、顺子问题

659. 分割数组为连续子序列

给你一个按 非递减顺序 排列的整数数组 nums 。

请你判断是否能在将 nums 分割成 一个或多个子序列 的同时满足下述 两个 条件：

• 每个子序列都是一个 连续递增序列（即，每个整数 恰好 比前一个整数大 1 ）。
• 所有子序列的长度 至少 为 3 。

如果可以分割 nums 并满足上述条件，则返回 true ；否则，返回 false 。

示例 1：

输入：nums = [1,2,3,3,4,5]
输出：true
解释：nums 可以分割成以下子序列：
[1,2,3,3,4,5] --> 1, 2, 3
[1,2,3,3,4,5] --> 3, 4, 5

示例 2：

输入：nums = [1,2,3,3,4,4,5,5]
输出：true
解释：nums 可以分割成以下子序列：
[1,2,3,3,4,4,5,5] --> 1, 2, 3, 4, 5
[1,2,3,3,4,4,5,5] --> 3, 4, 5

示例 3：

输入：nums = [1,2,3,4,4,5]
输出：false
解释：无法将 nums 分割成长度至少为 3 的连续递增子序列。

思路：

我们需要对于元素进行分配，那些是需要自成一个子序列，那些是需要接到其他子序列的后面

所以情况有两种

• 当前元素 v 自成一派，「以自己开头」构成一个长度至少为 3 的序列。

• 当前元素 v 接到已经存在的子序列后面。

问题又来了如果元素两个条件都可以满足该怎么办。

这里是需要先判断是否可以接到其他子序列后面，在判断是否可以自成顺子

但是我们如何知道当前元素是需要自成顺子还是接到其他的顺子后面，这里肯定需要数据结构的辅助。

但是需要什么数据结构呢？

可以使用字典来辅助：一个字典counter用来判断当前元素的数量，另一个字典need用来判断那些数字需要接着其他子序列后面

class Solution:
    def isPossible(self, nums: List[int]) -> bool:
        """
        思路：
        我们遍历整个数字，判断数字是需要单成顺子还是作为其他顺子的后续
        这两个情况是需要又先后顺序的，需要先判断是否先为其他顺子的后续，在判断是否自成顺子

        我们如果满足这个情况呢。可以使用两个数据结构来辅助。
        counter用来判断当前字符串剩余的数量
        need 记录哪些元素可以被接到其他子序列后面
        """
        counter = Counter(nums)
        need = defaultdict(int)

        for num in nums:
            if counter[num] == 0:
                continue

            if need[num] > 0:
                counter[num] -= 1
                need[num] -= 1
                need[num + 1] += 1
            elif counter[num] > 0 and counter[num + 1] > 0 and counter[num + 2] > 0:
                counter[num] -= 1
                counter[num + 1] -= 1
                counter[num + 2] -= 1
                need[num + 3] += 1
            else:
                return False
        return True

如果需要判断把子序列都打印出来怎么办，这个时候need需要修改为记录那些子序列产生的需求

# need[6] = 2 说明有两个子序列需要 6
need = {}

# need[6] = [
#     [3,4,5],
#     [2,3,4,5],
# ]

class Solution:
    def isPossible(self, nums: List[int]) -> List[int]:
        counter = Counter(nums)
        need = defaultdict(list)
        result = []
        for num in nums:
            if counter[num] == 0:
                continue
            if len(need[num]) > 0:
                counter[num] -= 1
                temp = need[num].pop()
                temp.append(num)
                need[num + 1] += [temp]
            elif counter[num] > 0 and counter[num + 1] > 0 and counter[num + 2] > 0:
                counter[num] -= 1
                counter[num + 1] -= 1
                counter[num + 2] -= 1
                temp = [num, num + 1, num + 2]
                need[num + 3] += [temp]
            else:
                return result
        for key, val in need.items():
            result += val
        return result


print(Solution().isPossible([1, 2, 3, 3, 4, 4, 5, 5])) #[[3, 4, 5], [1, 2, 3, 4, 5]]

那么如果是求最大的顺子呢

我们可以使用动态规划的思路来解决

• dp[i]代表着i位置最长的顺子
• 递推公式：if nums[i] == nums[j] + 1: dp[i] = dp[j] + 1
• 初始化：每个数字都是一个长度为1的顺子
• 遍历顺序从左到右
• 打印dp

def max_length_subsequence(nums: List[int]):
    nums.sort()
    dp = [1] * len(nums)

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

    print(dp)
    return max(dp)