偃师建网站那家公司好,专业设计vi,wordpress用户中心,wordpress 主页 慢题目#xff1a;最长递增子序列的个数
给定一个未排序的整数数组#xff0c;找到最长递增子序列的个数。
示例 1
输入#xff1a;nums [1,3,5,4,7]输出#xff1a;2解释#xff1a;有两个最长递增子序列#xff0c;分别是 [1,3,4,7] 和 [1,3,5,7] 。
示例 2
输入最长递增子序列的个数
给定一个未排序的整数数组找到最长递增子序列的个数。
示例 1
输入nums [1,3,5,4,7]输出2解释有两个最长递增子序列分别是 [1,3,4,7] 和 [1,3,5,7] 。
示例 2
输入nums [2,2,2,2,2]输出5解释最长递增子序列的长度是 1并且存在 5 个长度为 1 的递增子序列因此输出 5。
提示
1 nums.length 2000-10^6 nums[i] 10^6
解题思路提示
状态定义 可以使用两个数组dp 数组用来记录以每个位置结尾的最长递增子序列的长度count 数组用来记录以每个位置结尾的最长递增子序列的个数。 状态转移方程 对于每个位置 i 遍历 0 到 i - 1 的位置 j 如果 nums[i] nums[j] 则可以更新 dp[i] 和 count[i] 。更新 dp[i] dp[i] max(dp[i], dp[j] 1) 。更新 count[i] 如果 dp[i] dp[j] 1 则 count[i] count[j] 如果 dp[i] dp[j] 1 则 count[i] count[j] 。 最终结果 遍历 dp 数组找到最长递增子序列的长度 maxLen 。再次遍历 count 数组将所有对应 dp 值为 maxLen 的 count 值累加起来得到最长递增子序列的个数. 代码实现Java
/*** ClassName:LongestIncreasingSubsequenceCount** Author 爱掉头发的小李* Create 2025/1/26 15:46* Version 1.0*/
public class LongestIncreasingSubsequenceCount {public int findNumberOfLIS(int[] nums) {// 如果数组为空直接返回 0if (nums null || nums.length 0) {return 0;}int n nums.length;// dp 数组用于记录以每个位置结尾的最长递增子序列的长度初始值都为 1int[] dp new int[n];// count 数组用于记录以每个位置结尾的最长递增子序列的个数初始值都为 1int[] count new int[n];// 初始化 dp 数组和 count 数组for (int i 0; i n; i) {dp[i] 1;count[i] 1;}// 填充 dp 数组和 count 数组for (int i 1; i n; i) {for (int j 0; j i; j) {if (nums[i] nums[j]) {// 如果当前元素可以接在前面的元素后面形成更长的递增子序列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];}}}}// 找到最长递增子序列的长度int maxLength 0;for (int len : dp) {maxLength Math.max(maxLength, len);}// 计算最长递增子序列的个数int result 0;for (int i 0; i n; i) {if (dp[i] maxLength) {result count[i];}}return result;}public static void main(String[] args) {LongestIncreasingSubsequenceCount solution new LongestIncreasingSubsequenceCount();int[] nums {1, 3, 5, 4, 7};System.out.println(solution.findNumberOfLIS(nums));}
}
代码说明 初始化部分 首先检查输入数组 nums 是否为空或长度为 0如果是则直接返回 0。初始化 dp 数组将每个元素初始化为 1因为每个元素自身可以构成一个长度为 1 的递增子序列。初始化 count 数组同样将每个元素初始化为 1表示以该元素结尾的长度为 1 的递增子序列的个数为 1。 双重循环填充 dp 和 count 数组 外层循环遍历数组中的每个元素从索引 1 开始。内层循环遍历当前元素之前的所有元素。如果当前元素 nums[i] 大于 nums[j]说明可以将 nums[i] 接在以 nums[j] 结尾的递增子序列后面 如果 dp[j] 1 大于 dp[i]则更新 dp[i] 为 dp[j] 1并将 count[i] 更新为 count[j]因为找到了更长的递增子序列。如果 dp[j] 1 等于 dp[i]说明找到了同样长度的递增子序列将 count[i] 加上 count[j]。 计算最长递增子序列的长度 遍历 dp 数组找到其中的最大值 maxLength即为最长递增子序列的长度。 计算最长递增子序列的个数 再次遍历 dp 数组将所有 dp[i] 等于 maxLength 的 count[i] 累加起来得到最长递增子序列的个数。
