Leetcode -673- The number of longest increasing subsequences

[Blog link]

The path to learning at 🐔

The nuggets home page

[答 案]

Topic link

[making address]

Making the address

[B].

Given an unsorted array of integers, find the number of longest incrementing subsequences.

Example 1:

Input: [1,3,5,4,7] Output: 2 Explanation: There are two longest increasing subsequences, which are [1,3, 4,7] and [1,3,5, 7].Copy the code

Example 2:

Input: [2,2,2,2,2] output: 5 explanation: the longest increasing subsequence is of length 1, and there are five subsequences of length 1, so output 5.Copy the code

Idea 1: sequence DP

• General sequence DP
• Because we’re dealing with the number of subsequences
• We need to define two DP arrays
  • Dp [I] represents the length of the longest increasing subsequence ending with the i-th character
  • CNT [I] represents the number of longest increasing subsequences ending with the i-th character
• Dp transfer process analysis
  • dp[0] = 1;
  • When nums[I] > nums[j] dp[I] = dp[j]+1
  • Whereas dp[I] = 1;
• Analysis of CNT transfer process
  • It is basically consistent with the above process analysis
  • cnt[0] =1 ;
  • whennums[i] > nums[j]When divided into two situations to judge
    • Determines whether the current element can be spelled after the previous element to form a new ascending subsequence
    • CNT [I] = CNT [j]; CNT [I] = CNT [j];
    • CNT [I] = CNT [j];
• Finally, return the maximum corresponding CNT value of DP

 public int findNumberOfLIS(int[] nums) {
           int[] dp = new int[nums.length];
           int[] cnt = new int[nums.length];
           dp[0] = 1;
           cnt[0] = 1;
           int max = 0;
           for(int i = 0; i < nums.length; i++){ dp[i] = cnt[i] =1;
               for(int j = 0; j < i; j++){if(nums[i]> nums[j]){
                       if(dp[i]<dp[j]+1){
                           cnt[i]=cnt[j];
                           dp[i] = dp[j]+1;
                       }else if(dp[i]== dp[j]+1){
                           cnt[i]+=cnt[j];
                       }
                   }
               }
               max = Math.max(dp[i],max);
           }
           int res = 0;
           for(int i = 0; i < nums.length; i++){
               if(max == dp[i]){ res +=cnt[i]; }}return res;

   }
Copy the code

• Time complexity :O(
  $n^2$)
• Space complexity :O(
  $n$)