Java实现 LeetCode 673 最长递增子序列的个数（递推）

怼烎@ 2023-07-22 03:50 7阅读 0赞

## 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;
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，7人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode-300. 最长递增子序列

目录动态规划题目来源 [300. 最长递增子序列][300.] 动态规划 1.确定dp数组（dp table）以及下标的含义 dp\

约定不等于承诺〃/ 2024年03月26日 21:12/ 0 赞/ 91 阅读

相关 LeetCode_动态规划_中等_673.最长递增子序列的个数

目录 1.题目 2.思路 3.代码实现（Java） 1.题目给定一个未排序的整数数组 nums ，返回最长递增子序列的个数。注意这个数列

我就是我/ 2023年10月06日 23:42/ 0 赞/ 24 阅读

相关 LeetCode - 300 最长递增子序列

目录题目来源题目描述示例提示题目解析算法源码 -------------------- 题目来源 [300. 最长递增子序列 - 力扣（Lee

绝地灬酷狼/ 2023年09月23日 15:35/ 0 赞/ 126 阅读

相关 Java实现 LeetCode 673 最长递增子序列的个数（递推）

673. 最长递增子序列的个数给定一个未排序的整数数组，找到最长递增子序列的个数。示例 1: 输入: \[1,3,5,4,7\] 输出: 2 解释: 有两

怼烎@/ 2023年07月22日 03:50/ 0 赞/ 8 阅读

相关 LeetCode 300. 最长递增子序列

[LeetCode 300. 最长递增子序列][LeetCode 300.] Idea 最长递增子序列，首先就想到了LCS（最长公共子序列），这个其实比最长公共子序列还

淩亂°似流年/ 2023年01月23日 07:59/ 0 赞/ 230 阅读

相关 LeetCode 300. 最长递增子序列

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

一时失言乱红尘/ 2022年10月26日 04:57/ 0 赞/ 185 阅读

相关 leetcode300. 最长递增子序列

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bmy5ZWl5ZWl5

曾经终败给现在/ 2022年09月12日 05:52/ 0 赞/ 223 阅读

相关最长递增子序列的个数

最长递增子序列的个数 package com.bingoabin.algorithm.dp; / @Author: xubin34 @Date:

我不是女神ヾ/ 2022年09月12日 03:57/ 0 赞/ 197 阅读

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

2021-09-20 LeetCode每日一题链接：[https://leetcode-cn.com/problems/number-of-longest-increa

叁歲伎倆/ 2022年09月12日 03:55/ 0 赞/ 131 阅读

相关 673 最长递增子序列的个数（动态规划-最长上升子序列）

1. 问题描述：给定一个未排序的整数数组，找到最长递增子序列的个数。示例 1: 输入: \[1,3,5,4,7\] 输出: 2 解释: 有两个最长递增子序列，

雨点打透心脏的1/2处/ 2022年09月02日 12:51/ 0 赞/ 223 阅读