專欄：50多種數據結構徹底征服

專欄：50多種經典圖論算法全部掌握

繼2月20號字節跳動發文稱要招聘4000+實習生之后，估計感覺人數不夠，于是在2月28號在次發文稱要再招1000+人，結果還是感覺不夠，3月3號在次發文稱還要再招1500+，招聘也真夠麻煩的，半個月內發布3次。

對于大三大四的學生這是一個很好的機會，有需要的可以點擊文章最下方原文鏈接即可去投遞。

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

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

問題描述

來源：LintCode第1093題

難度：中等

給定一個無序的整數序列，找到 最長的升序子序列的個數 。

示例1：

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

示例2：

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

問題分析

這題讓計算的是最長升序子序列的個數，在之前我們講過 ，這兩道題的解法都非常類似，我們還使用動態規劃來解決，具體實現原理可以看下前面的文章。

因為最長上升子序列可能不止一個，所以我們需要使用一個變量maxLen來記錄最長上升子序列的長度， 如果遇到相同長度的最長上升子序列就累加它的個數count，如果遇到更長的上升子序列，就更新maxLen和count的值 。

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

JAVA：

public int findNumberOfLIS(int[] nums) {
    // count：最長上升子序列的個數，maxLen：最長上升子序列的長度。
    int count = 0, maxLen = 0, len = nums.length;
    // dp[i]表示以nums[i]結尾的最長上升子序列的長度，
    // cnt[i]表示以nums[i]結尾的最長上升子序列的個數。
    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];// 累加最長上升子序列的個數。
                }
            }
        }
        // 如果有更長的上升子序列，就更新maxLen和count，否則如果以nums[i]
        // 結尾的最長上升子序列長度和maxLen一樣，就累加count的值。
        if (dp[i] > maxLen) {
            maxLen = dp[i];
            count = cnt[i];
        } else if (dp[i] == maxLen) {
            count += cnt[i];
        }
    }
    return count;
}

筆者簡介

博哥，真名：王一博，畢業十多年， 作者，專注于 數據結構和算法 的講解，在全球30多個算法網站中累計做題2000多道，在公眾號中寫算法題解800多題，對算法題有自己獨特的解題思路和解題技巧，喜歡的可以給個關注，也可以 下載我整理的1000多頁的PDF算法文檔 。