Re: [閒聊] 每日LeetCode

[yam276 (史萊哲林的優等生)]

※ 引述《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;
    }
}


--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 60.248.143.163 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1689933357.A.283.html
推 ILoveErr: 大師
→ a9486l: 大師