一、最长递增子序列的个数

""" 【动态规划】 673 给定一个未排序的整数数组，找到最长递增子序列的个数 (可不连续)。 输入: [1,3,5,4,7] 输出: 2 解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。 """

""" 【复杂度分析】 时间复杂度：O(N^2),其中 N 是 nums 的长度。 空间复杂度：O(N)，lengths 和 counts 所用的空间。 """

from typing import List
class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        L = len(nums)
        if L <=1:
            return L
        maxLen = [1] * L
        count = [1] *L

        for i in range(1, L):
            for j in range(0,i):
                if nums[j] < nums[i]:
                    if maxLen[j]+1 > maxLen[i]: # 等效成 maxLen[i] = max(maxLen[i], maxLen[j] + 1) 但是这样就不方便加其他语句
                        maxLen[i] = maxLen[j]+1
                        count[i] = count[j]
                    elif maxLen[j]+1 == maxLen[i]:
                        count[i] = count[i] + count[j]

        print("maxLen:",maxLen)
        print("count:", count)
        ans = 0
        max_maxLen = max(maxLen)           # ！！！ 先计算出来，防止在下面的for循环中反复计算，节省时间 ！！！
        for k in range(L):
            if maxLen[k] == max_maxLen:
               ans = ans + count[k]       # 有可能有重复的数，如 [1,3,5,4,7,7]

        return ans

if __name__ == '__main__':

    nums = [1,3,5,4,7,7]
    solution = Solution()
    ans = solution.findNumberOfLIS(nums)
    print("ans:",ans)

二、最长递增子序列的长度

""" 【动态规划】 "人人为我"递推型 时间复杂度 O(n^2) 674 给定一个未排序的整数数组，找到最长递增子序列的长度 (可不连续)。 输入: [1,3,5,4,7] 输出: 4 解释: 最长（不连续）递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7] 长度均为 4。 """

from typing import List
class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:

        L = len(nums)
        if L <=1:
            return L

        maxLen = [1] * L            # 存放每一个 maxLen[i]，最后一个 maxLen[-1]即所求答案

        for i in range(1,L):        # 每次求以第i个数 a(i)为 【终点】的最长上升子序列长度
            for j in range(0,i):    # 查看第i个数a(i)左边，以第 j 个数a(j)为终点的最长上升子序列
                if (nums[j] < nums[i]):  # 也就是在以 a[j]为终点的最长上升子序列的基础上加a[i]，即长度加1，也就是以a[i]为终点的最长上升子序列
                    maxLen[i] = max(maxLen[i], maxLen[j] + 1)  # maxLen[i] 至少可以是maxLen[j]+1，只有当maxLen[j]+1>maxLen[i],才更新maxLen[i]
                    # 所以上一句取max操作，等效成 if maxLen[j] + 1 > maxLen[i]: maxLen[i] = maxLen[j] + 1

                # else: # 这个else部分不正确
                # maxLen[i] = 1
        print("maxLen:",maxLen)
        return max(maxLen)

if __name__ == '__main__':

    nums = [1,3,5,4,7]
    #nums = [1, 5, 7, 9, 15, 10, 11,6, 2, 7]
    #nums = [1]
    solution = Solution()

    L = solution.findNumberOfLIS(nums)

    print(L)