首页 > 其他分享 >673. 最长递增子序列的个数

673. 最长递增子序列的个数

时间:2024-05-31 18:37:56浏览次数:24  
标签:count nums int 递增 个数 673 序列 dp

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

示例 1:
输入: [1,3,5,4,7]
输出: 2
解释: 有两个最长递增子序列,分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。

示例 2:
输入: [2,2,2,2,2]
输出: 5
解释: 最长递增子序列的长度是1,并且存在5个子序列的长度为1,因此输出5。

提示:
1 <= nums.length <= 2000
-10^6 <= nums[i] <= 10^6
package priv20240430.solution673;

public class Solution {
    public int findNumberOfLIS(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int[] dp = new int[nums.length];
        int[] count = new int[nums.length];
        int maxLen = 0,ans =0;
        for (int i = 0; i < nums.length; i++) {
            count[i] = 1;
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    if (dp[j] + 1 > dp[i]) {
                        dp[i] = dp[j] + 1;
                        count[i] = 1;
                    }else if(dp[j]+1 == dp[i]){
                        count[i] += count[j];
                    }
                }
            }
            if (dp[i] > maxLen){
                maxLen = dp[i];
                ans = count[i];
            }else if(dp[i] == maxLen){
                ans += count[i];
            }
        }
        return ans;
    }
}

 

 

标签:count,nums,int,递增,个数,673,序列,dp
From: https://www.cnblogs.com/xxaxf/p/18225081

相关文章

  • 我有一个数组 [ 1,2 , 3,-4,-1,4 ],希望按 [-4,1,-1,2,3,4] 的顺序排列。
    我有一个数组[1,2,3,-4,-1,4],希望按照[-4,1,-1,2,3,4]的顺序排序。想要按照负数、正数、绝对值大小排序。我可以帮实现。以下是使用Python代码实现此排序逻辑的方法:defspecial_sort(nums):"""按照负数、正数、绝对值大小排序。Args:nu......
  • 有1,2,3,4这四个数字,能组成多少个互不相同且无重复数字的三个数?分别是什么?
    有1,2,3,4这四个数字,能组成多少个互不相同且无重复数字的三个数?分别是什么?提示:123,321就是符合要求,数字既不相同,而且每个数字的个十百位也不重复;而121,212就不行,因为数字的各位与百位重复123,124,134,213,214,234result=0count=0#取百位上的数字foriinrange(1,5):#获取十位......
  • lammps统计六元环(非苯环)个数--Python实现
    思路1、六元碳环中,两原子最远距离为3X1.7=5.12、六个碳原子的集合中,每个碳原子彼此之间都只成两个C-C键的情况。只有一种可能————碳原子之间首尾相连连成六元环步骤1、找出距离目标原子距离<=5的所有原子,建立一个包含n个原子列表2、在列表中随机取六个原子,建立一个小......
  • leedcode【349】. 两个数组的交集——Java解法
    Problem: 349.两个数组的交集题目思路解题方法复杂度Code效果题目给定两个数组nums1和nums2,返回它们的交集。输出结果中的每个元素一定是唯一的。我们可以不考虑输出结果的顺序。示例1:输入:nums1=[1,2,2,1],nums2=[2,2]输出:[2]示例2:输入:nums1=[......
  • Day 6| 242.有效的字母异位词 、349. 两个数组的交集 、 202. 快乐数 、 1. 两数之和
    242.有效的字母异位词建议:这道题目,大家可以感受到数组用来做哈希表给我们带来的遍历之处。题目链接/文章讲解/视频讲解:https://programmercarl.com/0242.有效的字母异位词.html思考很简单的一道题,需要记住python获取ascii值的函数时ord()classSolution:defisAnag......
  • 代码随想录算法训练营第五天|242(有效的字母异位词),349(两个数组的交集),202(快乐数)
    哈希C#常用的数据结构:[]Array,ArrayList数组和动态数组List集合HashSet哈希集合(无重复值)HashTable哈希表(obj,obj的键值对)Dictionary<T,T>泛型的哈希表什么时候考虑Hash数据结构?需要高效的判断一个值是否存在在一个容器中时。容器不允许重复值(HashSet或哈希表的......
  • 赛克oj 1541(线性筛、约数个数)
    赛氪OJ-专注于算法竞赛的在线评测系统(saikr.com)题目描述小明在学校学了质数和合数的知识后,便想知道对于任意的一个数N,将其拆分为一个质数与一个合数相加的结果,有几种拆法?但后来想想又觉得太简单了,于是他追加了一些条件,合数要继续拆分为两个数相乘的形式才行,那么满足以上......
  • 算法训练 | 二叉树Part3 | 104.二叉树的最大深度、111.二叉树的最小深度、222.完全二
    目录104.二叉树的最大深度递归法⭐迭代法111.二叉树的最小深度递归法⭐迭代法222.完全二叉树的节点个数普通二叉树完全二叉树嵌入式学习分享个人主页:Orion嵌入式随想录-小红书(xiaohongshu.com)104.二叉树的最大深度题目链接:104.二叉树的最大深度-力扣(Le......
  • 设线性表中每个元素有两个数据项k1和k2,现对线性表按一下规则进行排序:先看数据项k1,k1
    题目:设线性表中每个元素有两个数据项k1和k2,现对线性表按一下规则进行排序:先看数据项k1,k1值小的元素在前,大的在后;在k1值相同的情况下,再看k2,k2值小的在前,大的在后。满足这种要求的排序方法是()A.先按k1进行直接插入排序,再按k2进行简单选择排序B.先按k2进行直接插入排序,再按k1进行......
  • 链式二叉树的前,中,后序遍历 AND 结点个数及高度等 文末附带全部代码
    目录前言1.前序遍历2.中序遍历3.后续遍历4.二叉树结点的个数5.二叉树叶子结点个数6.二叉树的高度7.二叉树第K层结点的个数8.二叉树查找值为x的结点全部代码总结正文开始前言本文旨在介绍二叉树的链式存储中一些函数的实现博客主页:酷酷学!!!更多文章,......