Find the longest increasing number of subsequence is not the length!!

Small knowledge, big challenge! This paper is participating in theEssentials for programmers”Creative activities

Code shrimp is a sand carving and funny boy who likes listening to music, playing games and writing as well as most of his friends. The days are still very long, let’s refuel our efforts together 🌈

✨ topic

673. Number of longest increasing subsequences

🤣 digression

The number of the longest increasing subsequence, not the length of the longest increasing subsequence.No, no, no (￣▽￣)

Don’t ask me how I know (manual funny)

300. Eldest son sequence

class Solution {

    public int lengthOfLIS(int[] nums) {

        int[] dp = new int[nums.length];

        for(int i = 0; i < nums.length; i++) { dp[i] =1;
        }

        int res = 1;
        for(int i = 1; i < nums.length; i++) {for(int j = 0; j < i; j++) {if(nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i],dp[j] + 1);
                }
            }
            res = Math.max(res,dp[i]);
        }

        returnres; }}Copy the code

😉 serious point, solution idea

The answer to this question isThe number of longest increasing subsequences, so we have to know what the longest is, to find the longest sequence number is!

Using dynamic programming, setint[] dp = new int[nums.length]; Array record lengthTo set upint[] counts = new int[nums.length]; Record the number of

So how does the state transition ❔

If there is familiarity300. Eldest son sequenceAs your friends may know, I don’t talk nonsense

Because we want to increment, so ⏬ whenDp [j] + 1 > dp[I] + 1 > dp[I] If true, dp[j] should not be preceded by dp[I]. If dp[I] is longer than dp[I], then I need to update the length

But if theDp [j] + 1 == dp[I], dp[j] + 1 == dp[I]

🌈 code implementation

class Solution {
    public int findNumberOfLIS(int[] nums) {
        int len = nums.length;
        if (len <= 1) return len;
        int[] dp = new int[len]; 
        int[] counts = new int[len]; 

        // The length must be at least 1
        Arrays.fill(counts, 1);

        int maxLen = 0;

        for (int i = 0; i < len; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    if (dp[j] + 1 > dp[i]) {
                        dp[i] = dp[j] + 1;
                        counts[i] = counts[j];
                    }else if (dp[j] + 1 == dp[i]) {
                        counts[i] += counts[j];
                    }
                }
            }
            maxLen = Math.max(maxLen,dp[i]);
        }

        // Select maxLen from maxLen
        int res = 0;
        for (int i = 0; i < len; ++i) {
            if(dp[i] == maxLen) { res += counts[i]; }}returnres; }}Copy the code

🔥 Featured column

Self-introduction, to everyone recommend their column 😁, welcome small partners to collect attention 😊

Force link algorithm problem solving area

The small white to learn Java

MybatisPlus column

App crawler Column

PC side crawler column

Big factory interview question column

💖 finally

I am aCode pipi shrimp, a prawns lover who loves to share knowledge, will update useful blog posts in the future, looking forward to your attention!!

Creation is not easy, if this blog is helpful to you, I hope you can == one key three even oh! Thank you for your support. See you next time