当前位置:网站首页>LeetCode:673. 最长递增子序列的个数
LeetCode:673. 最长递增子序列的个数
2022-07-06 08:44:00 【Bertil】
给定一个未排序的整数数组 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
解题思路
1.首先初始化两个数组:状态dp[i]表示以nums[i] 结尾的最长上升子序列的长度,count[i] 表示以nums[i] 结尾的最长上升子序列的个数
2.然后找到最长子序列并且做好标记
3.最后统计最长子序列出现的次数并且返回
代码
/** * @param {number[]} nums * @return {number} */
var findNumberOfLIS = function(nums) {
// 初始化dp数组
let len = nums.length;
let dp = Array(len).fill(1);
let count = Array(len).fill(1);
let res = 0;
// 找到最长子序列并做好标记
for(let i = 0; i < len; i++) {
for(let j = 0; j < i; j++) {
if(nums[i] > nums[j]) {
// Math.max...的写法
if(dp[j]+1 > dp[i]) {
dp[i] = dp[j]+1
count[i] = count[j] // 最长递增子序列的个数
// 其实就是考虑相等的情况
}else if(dp[j]+1 === dp[i]) {
count[i] += count[j]
}
}
}
}
// 统计一下 max 出现的次数
let max = Math.max(...dp);
// 这里想要统计所有LIS的个数就要遍历
for (let i = 0; i < len; i ++) if(dp[i] === max) res += count[i];
return res;
};
边栏推荐
- 704 二分查找
- 移位运算符
- Promise 在uniapp的简单使用
- Bottom up - physical layer
- logback1.3. X configuration details and Practice
- vb.net 随窗口改变,缩放控件大小以及保持相对位置
- After PCD is converted to ply, it cannot be opened in meshlab, prompting error details: ignored EOF
- Esp8266-rtos IOT development
- vb. Net changes with the window, scales the size of the control and maintains its relative position
- Deep analysis of C language pointer
猜你喜欢
查看局域网中电脑设备
Delay initialization and sealing classes
【嵌入式】使用JLINK RTT打印log
2022.02.13 - 238. Maximum number of "balloons"
JVM performance tuning and practical basic theory - Part 1
【ROS】usb_ Cam camera calibration
marathon-envs项目环境配置(强化学习模仿参考动作)
Deep analysis of C language data storage in memory
tree树的精准查询
Precise query of tree tree
随机推荐
torch建立的网络模型使用torchviz显示
【MySQL】鎖
R language ggplot2 visualization, custom ggplot2 visualization image legend background color of legend
egg. JS getting started navigation: installation, use and learning
What is CSRF (Cross Site Request Forgery)?
Bottom up - physical layer
Target detection - pytorch uses mobilenet series (V1, V2, V3) to build yolov4 target detection platform
目标检测——Pytorch 利用mobilenet系列(v1,v2,v3)搭建yolov4目标检测平台
FairGuard游戏加固:游戏出海热潮下,游戏安全面临新挑战
Verrouillage [MySQL]
C語言雙指針——經典題型
Shift Operators
[MySQL] log
gcc动态库fPIC和fpic编译选项差异介绍
Generator parameters incoming parameters
MySQL learning records 12jdbc operation transactions
Unsupported operation exception
Colorlog combined with logging to print colored logs
PC easy to use essential software (used)
Roguelike game into crack the hardest hit areas, how to break the bureau?