[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)

	class Solution {
	fun findNumberOfLIS(nums: IntArray): Int {
	val len = IntArray(nums.size){1}
	val count = IntArray(nums.size){1}
	var longest = Int.MIN_VALUE
	for(i in nums.indices) {
	for (j in 0 until i) {
	if(nums[j] < nums[i]) {
	if(len[j] + 1 > len[i]) {
	//>> find longer subsequence
	len[i] = len[j] + 1
	count[i] = count[j]
	} else if(len[j] + 1 == len[i]) {
	//>> another subsequence will have the same length after including nums[i]
	count[i] += count[j]
	}
	}
	}
	longest = Math.max(longest, len[i])
	}
	var ans = 0
	for(i in len.indices) {
	if(len[i] == longest) {
	ans += count[i]
	}
	}
	return ans
	}
	}

view raw number_of_longest_increasing_subsequence.kt hosted with ❤ by GitHub