※ 引述《Rushia (みけねこ的鼻屎)》之铭言：
: https://leetcode.com/problems/number-of-longest-increasing-subsequence/description/
: 673. Number of Longest Increasing Subsequence
: 给你一个阵列找出这个阵列的最长递增子序列共有几个，递增为严格递增。
: 思路：
: 1. [300. Longest Increasing Subsequence] 这题的延伸版本，原题目只要求长度
: 现在要求有几个，dp 的思路是如果我们知道 i 之前的所有最长递增子序列长度，
: 则 dp[i] 的最长子序列长度只需要找满足 nums[j] < nums[i] 且 j < i 的 j
: 并取 dp[j] 的最大值加一就是 dp[i] 的 LIS。
: 2.只需要把原题目在算 dp 的时候顺便统计这个长度的序列有几个即可，当遇到更大
: 的长度就更新长度并重置当前计数，遇到一样的长度则累加。
写完了感觉还是只懂一半
知道在干嘛但要我自己写可能会卡住
:(
Code:
impl Solution
{
pub fn find_number_of_lis(nums: Vec<i32>) -> i32
{
let nums_size = nums.len();
if nums_size == 0
{
return 0;
}
let mut LIS_lengths: Vec<i32> = vec![1; nums_size];
let mut LIS_nums: Vec<i32> = vec![1; nums_size];
let mut max_LIS_lengths: i32 = 1;
for i in 0..nums_size
{
for j in 0..i
{
if nums[i] > nums[j]
{
if (LIS_lengths[j] + 1) > LIS_lengths[i]
{
LIS_lengths[i] = LIS_lengths[j] + 1;
LIS_nums[i] = LIS_nums[j];
}
else if (LIS_lengths[j] + 1) == LIS_lengths[i]
{
LIS_nums[i] += LIS_nums[j];
}
}
}
max_LIS_lengths = max_LIS_lengths.max(LIS_lengths[i]);
}
let mut result: i32 = 0;
for i in 0..nums_size
{
if LIS_lengths[i] == max_LIS_lengths
{
result += LIS_nums[i];
}
}
return result;
}
}