Java实现 LeetCode 673 最长递增子序列的个数(递推)
2024-10-09 05:37:53
673. 最长递增子序列的个数
给定一个未排序的整数数组,找到最长递增子序列的个数。
示例 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。
注意: 给定的数组长度不超过 2000 并且结果一定是32位有符号整数。
PS:
普通递推,加一个记录的数组
class Solution {
public int findNumberOfLIS(int[] nums) {
if (nums.length == 0) {
return 0;
}
int[] dp = new int[nums.length];
int[] combination = new int[nums.length];
Arrays.fill(dp, 1);
Arrays.fill(combination, 1);
int max = 1, res = 0;
for (int i = 1; i < dp.length; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
if (dp[j] + 1 > dp[i]) {
dp[i] = dp[j] + 1;
combination[i] = combination[j];
} else if (dp[j] + 1 == dp[i]) {
combination[i] += combination[j];
}
}
}
max = Math.max(max, dp[i]);
}
for (int i = 0; i < nums.length; i++)
if (dp[i] == max) res += combination[i];
return res;
}
}
最新文章
- 为什么说基于TCP的移动端IM仍然需要心跳保活?
- ViewPager做图片浏览器,加载大量图片OOM的问题修正
- Android安装BusyBox(三星N7108)
- vijos1037搭建双塔(一维背包问题)
- 解决umount.nfs: /data: device is busy 问题
- devexpress 数据导入(gridcontrol 导出 csv)
- 如何保护你的linux操作系统
- ionic tabs-top
- Reactor模式
- UISenior之数据的本地化持久化
- css media
- libcurl的封装,支持同步异步请求,支持多线程下载,支持https
- flex与js相互调用
- Untiy文档总结(1)-Profiling
- 【转】Swagger2 添加HTTP head参数
- spring data jpa、Hibernate开启全球唯一UUID设置
- CatBoost算法和调参
- Vijos1982 NOIP2015Day2T2 子串 substring 动态规划
- Sprint 冲刺第三阶段第6-10天
- ES6学习笔记<;三>; 生成器函数与yield