【算法】【动规】最长递增子序列的个数

---

跳转汇总链接

👉🔗动态规划算法汇总链接

---

demo：在一次遍历中，求出最大值出现的次数

总体思路：

• 用一个变量 numMax 储存遍历中遇到的最大值，并同时在 num[i] == numMax 相等的时候对计数变量 count 进行 ++ 操作；
• 可我们在遍历的时候无法确定此时遇见的“最大值”是否是最终的“最大值”，所以需要在每次 num[i] > numMax 的时候更新 numMax，并重置 count；

所以要分情况进行讨论：

if(nums[i] == numMax) count++；
if(nums[i] > numMax) count = 1, numMax = nums[i];

最长递增子序列的长度 + 在一次遍历中，求出最大值出现的次数
就是如下题目的拆解逻辑。

---

2.3 最长递增子序列的个数

🔗题目链接

给定一个未排序的整数数组 nums，返回最长递增子序列的个数 。
注意 这个数列必须是 严格 递增的。

1. 状态表示
   • 本题依旧以 字符串上 i 位置为结尾作为一个状态；
   • len[i] 表示，以 i 位置为结尾的 最长递增子字符串的长度；
   • count[i] 表示，以 i 位置为结尾的 最长递增子字符串长度的个数。
2. 状态转移方程

   • len[i] 分成两种情况，第一种是自身，第二种是之前的最大递增子序列+自身（之前分析过，可以参考👉🔗题目2.1 链接在此）

   • 设以 i 位置结尾的子序列，他的倒数第二个位置为 j (0 <= j < i)，count[i] 要根据 len[i] 和 len[j] 的情况来填写，具体见本篇 demo

   • 两者结合起来考虑：

     长度为1，count[i] = len[i] = 1
     长度大于1，if nums[j] <= nums[i]
     			if len[j]+1 == len[i], count[i] += count[j]
     			if len[j]+1 > len[i], len[i] = len[j]+1, count[i] = count[j];
     

3. 初始化
   • 两张表全初始化为 1。
4. 填表顺序
   • 两张表同时，从左往右依次填写。
5. 返回值
   • len 表中所以最大值出现的位置，对于 count 表上的值相加，就是需要返回的内容，也是 demo 的思想（具体看代码吧~）

class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> len(n,1);
        auto count = len;
        int lenMax = 1, retCount = 1;
        for(int i = 1; i < n; i++)
        {
            for(int j = 0; j < i; j++)
            {
                if(nums[j] < nums[i])
                {
                    if(len[j]+1 == len[i])
                    {
                        count[i] += count[j];
                    }
                    else if(len[j]+1 > len[i])
                    {
                        count[i] = count[j];
                        len[i] = len[j] + 1;
                    }
                }
            }
            if(lenMax == len[i])
            {
                retCount += count[i];
            }
            else if(lenMax < len[i])
            {
                lenMax = len[i];
                retCount = count[i];
            }
        }
        return retCount;
    }
};

---

🥰如果本文对你有些帮助，欢迎👉 点赞 收藏 关注，你的支持是对作者大大莫大的鼓励！！(????) 若有差错恳请留言指正~~

---