673. Number of Longest Increasing Subsequence

673. Number of Longest Increasing Subsequence

Given an unsorted array of integers, find the number of longest increasing subsequence.

Example 1:

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

Example 2:

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

Note: Length of the given array will be not exceed 2000 and the answer is guaranteed to be fit in 32-bit signed int.

思路：Dynamic Programming Intuition and Algorithm

Suppose for sequences ending at nums[i], we knew the length length[i] of the longest sequence, and the number count[i] of such sequences with that length.

For every i < j with A[i] < A[j], we might append A[j] to a longest subsequence ending at A[i]. It means that we have demonstrated count[i] subsequences of length length[i] + 1.

Now, if those sequences are longer than length[j], then we know we have count[i] sequences of this length. If these sequences are equal in length to length[j], then we know that there are now count[i] additional sequences to be counted of that length (ie. count[j] += count[i]).

class Solution { public int findNumberOfLIS(int[] nums) { int N = nums.length; if (N <= 1) return N; int[] lengths = new int[N]; //lengths[i] = length of longest ending in nums[i] int[] counts = new int[N]; //count[i] = number of longest ending in nums[i] Arrays.fill(counts, 1); for (int j = 0; j < N; ++j) { for (int i = 0; i < j; ++i) { if (nums[i] < nums[j]) { if (lengths[i] >= lengths[j]) { lengths[j] = lengths[i] + 1; counts[j] = counts[i]; } else if (lengths[i] + 1 == lengths[j]) { counts[j] += counts[i]; } } } } int longest = 0, ans = 0; for (int length: lengths) { longest = Math.max(longest, length); } for (int i = 0; i < N; ++i) { if (lengths[i] == longest) { ans += counts[i]; } } return

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。