求最少的递减子序列个数及子序列

给一个序列7,3,6,2,5,1，将其划分成数个递减子序列，要求子序列个数尽可能少，输出序列数和每个序列(序列元素用逗号分隔)

用例1

input:7,3,6,2,5,1
output:
2
7,3,2,1
6,5

用例2（反例）

input:7,3,6,2,5,1
output:
2
7,6,5
3,2,1
# 解释：虽然3和6都比7小，但是7后面是最近的是3，构造递减子序列不能跳过3

思路：dp

一开始以为是用dp直接求最长递减序列，然后求第二长的递减序列，后来发现不符合题意

用到非常巧妙的dp，逆向思维向求递增序列的dp数组，dp[i]表示nums[0...i]构成的最长递增序列长度

长度为1的为一组输出，2的为一组，依次类推：

dp[i]==1表示前面没有数字小于等于num[i]，即dp[i]==1的数字可以组成一个递减序列

dp[i]==2表示前面只有一个数字小于等于num[i]，而这个数字已经归入dp[i]==1这组了，因此dp[i]==2的数字又可以组成一个递减序列

以此类推。

注意：求dp时与递增序列稍微不同，多了等号，对于存在重复数字的用例7,3,6,2,5,1,8,4,3，两个3必然不能分在同一组，因此nums[j] == nums[i]时也要更新dp

inputstr = "7,3,6,2,5,1,9"	#某个用例
nums = [int(i) for i in inputstr.split(',')]
dp = [0 for i in range(len(nums))]
ans = 0
n = len(nums)
for i in range(n):
    dp[i] = 1
    for j in range(i):
        if nums[j] <= nums[i]:	#注意与求递增序列稍微不同，多了等号
            dp[i] = max(dp[i], dp[j] + 1)
            ans = max(dp[i], ans)
if ans == 0:
    print(1)
else:
    print(ans)
result = []
for i in range(1, max(dp)+1):
    result.append([])
    for j in range(len(dp)):
        if dp[j] == i:
            result[i-1].append(str(nums[j]))
for x in result:
    print(','.join(x))