Leetcode673。最長増加部分列の数



Leetcode 673 Number Longest Increasing Subsequences



ソートされていない整数配列が与えられた場合、最長増加部分列の数を見つけます。

Example 1: Input: [1,3,5,4,7] Output: 2 Explanation: There are two longest increasing subsequences, namely [1, 3, 4, 7] and [1, 3, 5, 7]. Example 2: Input: [2,2,2,2,2] Output: 5 Explanation: The length of the longest increasing subsequence is 1, and there are 5 subsequences with a length of 1, so 5 is output.

注:指定された配列の長さは2000を超えず、結果は32ビットの符号付き整数である必要があります。




アイデア

動的計画法

ここで問題となるのは、最長増加シーケンスの数を見つけることです。2つの配列を維持します。



len [i]、増加するシーケンスのテール要素としてiを使用して最長のシーケンス長を格納します(最長のシーケンスに注意してください)
cnt [i]、増加するシーケンスのテール要素としてiを使用して最長のシーケンスの番号を格納します(最長のシーケンスに注意してください)

二重ループを使用して、数値num [i]ごとに、iより前の数値から増加するシーケンスを見つけようとします。
例:1 2 3 5 4 7
4の場合、前の番号が4で増加するシーケンスを形成する1、2、3があり、1、2、3で終わる最長のシーケンスの長さを分析し、そのうちの1つを選択します。最長はプラス1です。現在の最長シーケンス長として。最長のシーケンスが複数ある場合、現在の最長のシーケンス番号は、前の最長のシーケンス長の合計です。

class Solution { public int findNumberOfLIS(int[] nums) { int n=nums.length int[] len=new int[n] int[] cnt=new int[n] for(int i=0i<ni++){ len[i]=cnt[i]=1 for(int j=0j<ij++){ if(nums[i]>nums[j]){ if(len[i]<len[j]+1){ len[i]=len[j]+1 cnt[i]=cnt[j] } else if(len[i]==len[j]+1){ cnt[i]+=cnt[j] } } } } int max_len=0,res=0 for(int t:len)max_len=Math.max(max_len,t) for(int i=0i<ni++){ if(len[i]==max_len){ res+=cnt[i] } } return res } }