当前位置:网站首页>LeetCode:673. Number of longest increasing subsequences
LeetCode:673. Number of longest increasing subsequences
2022-07-06 08:50:00 【Bertil】
Given an array of unsorted integers nums , Returns the number of longest increasing subsequences .
Be careful This sequence must be Strictly Incremental .
Example 1:
Input : [1,3,5,4,7]
Output : 2
explain : There are two longest increasing subsequences , Namely [1, 3, 4, 7] and [1, 3, 5, 7].
Example 2:
Input : [2,2,2,2,2]
Output : 5
explain : The length of the longest increasing subsequence is 1, And it exists 5 The length of the subsequence is 1, So output 5.
Tips :
- 1 <= nums.length <= 2000
- -10^6 <= nums[i] <= 10^6
Their thinking
1. First initialize two arrays : state dp[i] Said to nums[i] The length of the longest ascending subsequence at the end ,count[i] Said to nums[i] Number of longest ascending subsequences at the end
2. Then find the longest subsequence and mark it
3. Finally, count the number of occurrences of the longest subsequence and return
Code
/** * @param {number[]} nums * @return {number} */
var findNumberOfLIS = function(nums) {
// initialization dp Array
let len = nums.length;
let dp = Array(len).fill(1);
let count = Array(len).fill(1);
let res = 0;
// Find the longest subsequence and mark it
for(let i = 0; i < len; i++) {
for(let j = 0; j < i; j++) {
if(nums[i] > nums[j]) {
// Math.max... Writing
if(dp[j]+1 > dp[i]) {
dp[i] = dp[j]+1
count[i] = count[j] // The number of longest increasing subsequences
// In fact, it is to consider the equal situation
}else if(dp[j]+1 === dp[i]) {
count[i] += count[j]
}
}
}
}
// Statistics max Number of occurrences
let max = Math.max(...dp);
// Here I want to count all LIS The number of must be traversed
for (let i = 0; i < len; i ++) if(dp[i] === max) res += count[i];
return res;
};
边栏推荐
- 电脑清理,删除的系统文件
- marathon-envs项目环境配置(强化学习模仿参考动作)
- The network model established by torch is displayed by torch viz
- [embedded] print log using JLINK RTT
- 项目连接数据库遇到的问题及解决
- Tcp/ip protocol
- Swagger setting field required is mandatory
- 【ROS】usb_ Cam camera calibration
- Image, CV2 read the conversion and size resize change of numpy array of pictures
- Problems encountered in connecting the database of the project and their solutions
猜你喜欢
Excellent software testers have these abilities
广州推进儿童友好城市建设,将探索学校周边200米设安全区域
Target detection - pytorch uses mobilenet series (V1, V2, V3) to build yolov4 target detection platform
电脑清理,删除的系统文件
win10系统中的截图,win+prtSc保存位置
The harm of game unpacking and the importance of resource encryption
ESP8266-RTOS物联网开发
Mongodb installation and basic operation
pytorch训练好的模型在加载和保存过程中的问题
Deep analysis of C language data storage in memory
随机推荐
Sublime text using ctrl+b to run another program without closing other runs
Excellent software testers have these abilities
How to conduct interface test? What are the precautions? Nanny level interpretation
【剑指offer】序列化二叉树
LeetCode:162. 寻找峰值
Navicat premium create MySQL create stored procedure
Roguelike game into crack the hardest hit areas, how to break the bureau?
R language ggplot2 visualization, custom ggplot2 visualization image legend background color of legend
Browser thread
LeetCode:剑指 Offer 42. 连续子数组的最大和
项目连接数据库遇到的问题及解决
LeetCode:498. 对角线遍历
Navicat Premium 创建MySql 创建存储过程
力扣每日一题(二)
What is CSRF (Cross Site Request Forgery)?
pytorch训练好的模型在加载和保存过程中的问题
Using C language to complete a simple calculator (function pointer array and callback function)
Warning in install. packages : package ‘RGtk2’ is not available for this version of R
R language ggplot2 visualization: place the title of the visualization image in the upper left corner of the image (customize Title position in top left of ggplot2 graph)
vb. Net changes with the window, scales the size of the control and maintains its relative position