[LeetCode] 673. Number of Longest Increasing Subsequence

轉自LeetCode

Given an integer array nums, return the number of longest increasing subsequences.

Notice that the sequence has to be strictly increasing.

 

Example 1:

Input: nums = [1,3,5,4,7]
Output: 2
Explanation: The two longest increasing subsequences are [1, 3, 4, 7] and [1, 3, 5, 7].

Example 2:

Input: nums = [2,2,2,2,2]
Output: 5
Explanation: The length of longest continuous increasing subsequence is 1, and there are 5 subsequences' length is 1, so output 5.

 

Constraints:

• 1 <= nums.length <= 2000
• -106 <= nums[i] <= 106

Solution

300. Longest Increasing Subsequence 的衍生題，這次要求 longest increasing subsequence 有幾個

想法是，用兩個 DP arrays 來計算

一個是 len[i]，代表以 nums[i] 結尾的 LIS 的最長長度

另一個是 count[i]，代表以 nums[i] 結尾的 LIS 有幾個

最後只要把 len裡面等於最長長度的個數，全部加起來就是答案

kotlin，O(n^2)