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

2023-12-20 09:01:37

跳转汇总链接

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


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;
    }
};

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


文章来源:https://blog.csdn.net/m0_67470729/article/details/135088713
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。