專欄：50多種數(shù)據(jù)結(jié)構(gòu)徹底征服

專欄：50多種經(jīng)典圖論算法全部掌握

繼2月20號字節(jié)跳動發(fā)文稱要招聘4000+實(shí)習(xí)生之后，估計(jì)感覺人數(shù)不夠，于是在2月28號在次發(fā)文稱要再招1000+人，結(jié)果還是感覺不夠，3月3號在次發(fā)文稱還要再招1500+，招聘也真夠麻煩的，半個(gè)月內(nèi)發(fā)布3次。

對于大三大四的學(xué)生這是一個(gè)很好的機(jī)會，有需要的可以點(diǎn)擊文章最下方原文鏈接即可去投遞。

--------------下面是今天的算法題--------------

來看下今天的算法題，這題是LintCode的第1093題：最長升序子序列的個(gè)數(shù)。

問題描述

來源：LintCode第1093題

難度：中等

給定一個(gè)無序的整數(shù)序列，找到 最長的升序子序列的個(gè)數(shù) 。

示例1：

輸入: [1,3,5,4,7] 輸出: 2 解釋: 兩個(gè)最長的升序子序列分別是 [1, 3, 4, 7] 和 [1, 3, 5, 7].

示例2：

輸入: [2,2,2,2,2] 輸出: 5 解釋: 最長的連續(xù)升序子序列是1，有5個(gè)子序列的長度是1，所以輸出5.

問題分析

這題讓計(jì)算的是最長升序子序列的個(gè)數(shù)，在之前我們講過 ，這兩道題的解法都非常類似，我們還使用動態(tài)規(guī)劃來解決，具體實(shí)現(xiàn)原理可以看下前面的文章。

因?yàn)樽铋L上升子序列可能不止一個(gè)，所以我們需要使用一個(gè)變量maxLen來記錄最長上升子序列的長度， 如果遇到相同長度的最長上升子序列就累加它的個(gè)數(shù)count，如果遇到更長的上升子序列，就更新maxLen和count的值 。

比如數(shù)組[1, 3, 5, 4, 7, 6]中，以 7 結(jié)尾的最長上升子序列分別是[1,3,5,7]和[1,3,4,7]，以 6 為結(jié)尾的最長上升子序列分別是[1,3,5,6]和[1,3,4,6]，他們的長度都是 4 ，所以需要累加。

JAVA：

public int findNumberOfLIS(int[] nums) {
    // count：最長上升子序列的個(gè)數(shù)，maxLen：最長上升子序列的長度。
    int count = 0, maxLen = 0, len = nums.length;
    // dp[i]表示以nums[i]結(jié)尾的最長上升子序列的長度，
    // cnt[i]表示以nums[i]結(jié)尾的最長上升子序列的個(gè)數(shù)。
    int[] dp = new int[len];
    int[] cnt = new int[len];
    for (int i = 0; i < len; i++) {
        dp[i] = 1;// 長度至少是 1
        cnt[i] = 1;
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                if (dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;// 更新最長上升子序列的長度。
                    cnt[i] = cnt[j];
                } else if (dp[j] + 1 == dp[i]) {
                    cnt[i] += cnt[j];// 累加最長上升子序列的個(gè)數(shù)。
                }
            }
        }
        // 如果有更長的上升子序列，就更新maxLen和count，否則如果以nums[i]
        // 結(jié)尾的最長上升子序列長度和maxLen一樣，就累加count的值。
        if (dp[i] > maxLen) {
            maxLen = dp[i];
            count = cnt[i];
        } else if (dp[i] == maxLen) {
            count += cnt[i];
        }
    }
    return count;
}

筆者簡介

博哥，真名：王一博，畢業(yè)十多年， 作者，專注于 數(shù)據(jù)結(jié)構(gòu)和算法 的講解，在全球30多個(gè)算法網(wǎng)站中累計(jì)做題2000多道，在公眾號中寫算法題解800多題，對算法題有自己獨(dú)特的解題思路和解題技巧，喜歡的可以給個(gè)關(guān)注，也可以 下載我整理的1000多頁的PDF算法文檔 。