【Day 56 】2022-12-26 - 673. 最长递增子序列的个数

[azl397985856]

673. 最长递增子序列的个数

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/number-of-longest-increasing-subsequence/

前置知识

• 动态规划

  题目描述

  
  给定一个未排序的整数数组，找到最长递增子序列的个数。

示例 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。 注意: 给定的数组长度不超过 2000 并且结果一定是32位有符号整数。

[arinzz]

class Solution { public: int findNumberOfLIS(vector& nums) { vector<deque<pair<int,int>>> cnts({{{-1e9, 1}}}); vector sums({1});

    for(int i : nums) {
        auto pos = lower_bound(cnts.begin(), cnts.end(), i, [](auto& a, auto& b) {
            return a.back().first < b;
        }) - cnts.begin();

        while(cnts[pos-1].front().first >= i) {
            sums[pos-1] -= cnts[pos-1].front().second;
            cnts[pos-1].pop_front();
        }

        if(pos == cnts.size()) {
            cnts.push_back({});
            sums.push_back(0);
        }

        cnts[pos].push_back({i, sums[pos - 1]});
        sums[pos] += sums[pos - 1];
    }

    return sums.back();
}

};

[ringo1597]

代码

class Solution {
    public int findNumberOfLIS(int[] nums) {
        int n = nums.length, maxLen = 0, ans = 0;
        int[] dp = new int[n];
        int[] cnt = new int[n];
        for (int i = 0; i < n; ++i) {
            dp[i] = 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];
                    }
                }
            }
            if (dp[i] > maxLen) {
                maxLen = dp[i];
                ans = cnt[i]; // 重置计数
            } else if (dp[i] == maxLen) {
                ans += cnt[i];
            }
        }
        return ans;
    }
}

[buer1121]

class Solution: def findNumberOfLIS(self, nums: List[int]) -> int: n=len(nums) if n<=1: return n dp=[1]n count=[1]n maxCount=0

    for i in range(1,n):
        for j in range(i):
            if nums[i]>nums[j]:
                if dp[j]+1 > dp[i]:
                    dp[i]=dp[j]+1
                    count[i]=count[j]
                elif dp[j] + 1 == dp[i] :
                    count[i] += count[j]
            if dp[i] > maxCount:
                maxCount = dp[i]
    res=0
    for i in range(n):
        if dp[i]==maxCount:
            res+=count[i]
    return res

[zjsuper]

class Solution: def findNumberOfLIS(self, nums: List[int]) -> int:

need 2 dp

    #dp1[i]: store the lenth of longest sequence till i
    #dp2[i]: store the number of longest sequence till i
    dp1 = [1]*len(nums)
    dp2 = [1]*len(nums)
    longest = 1
    for i in range(1,len(nums)):
        for j in range(i):
            # nums[j]
            if nums[i] > nums[j]:
                if dp1[j] + 1 > dp1[i]:
                    dp1[i]  = dp1[j] + 1
                    dp2[i]  = dp2[j]
                elif dp1[j] + 1 == dp1[i]:
                    dp2[i] += dp2[j]

    longest = max(dp1)
    ans = 0
    for i in range(len(nums)):
        if dp1[i] == longest:
            ans += dp2[i]
    return ans

[whoam-challenge]

class Solution: def findNumberOfLIS(self, nums: List[int]) -> int: n, max_len, ans = len(nums), 0, 0 dp = [0] n cnt = [0] n for i, x in enumerate(nums): dp[i] = 1 cnt[i] = 1 for j in range(i): if x > nums[j]: if dp[j] + 1 > dp[i]: dp[i] = dp[j] + 1 cnt[i] = cnt[j] # 重置计数 elif dp[j] + 1 == dp[i]: cnt[i] += cnt[j] if dp[i] > max_len: max_len = dp[i] ans = cnt[i] # 重置计数 elif dp[i] == max_len: ans += cnt[i] return ans

[snmyj]

class Solution {
   public int findNumberOfLIS(int[] nums) {
        int len = nums.length;
        if(len <2){return len;}
        int[] dp = new int[len];
        int res=0;
        int maxCount=0;
        int[] counts = new int[len];
        for (int i = 0; i < dp.length; i++) {
            dp[i] = 1;
            counts[i] = 1;

        }

        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {

                if (nums[i] >nums[j]){
                    if (dp[j]+1 >dp[i]){

                        counts[i]= counts[j];
                    }else if (dp[j]+1 ==dp[i]){

                        counts[i]+=counts[j];
                    }

                    dp[i] = Math.max(dp[i],dp[j]+1);

                }

                if (dp[i] > maxCount){ 
                    maxCount = dp[i];
                }
            }

        }

        for (int i = 0; i < dp.length; i++) {
            if (dp[i]==maxCount){
                res+=counts[i];
            }
        }

        return res;
    }
}

[jackgaoyuan]

func findNumberOfLIS(nums []int) int {
    dp := make([]int, len(nums))
    count := make([]int, len(nums))
    // m: { key: 每个i的subMaxLength, value: subMaxLength的个数 }
    m := make(map[int]int)
    maxLength := 1
    for i := 0; i < len(dp); i++ {
        subMaxLength := 1
        subMap := make(map[int]int)
        subMap[1] = 1
        for j := 0; j < i; j++ {
            if nums[j] < nums[i] {
                subMap[dp[j] + 1] += count[j]
                if dp[j] + 1 > subMaxLength {
                    subMaxLength = dp[j] + 1
                }
            }
        }
        dp[i] = subMaxLength
        count[i] = subMap[subMaxLength]
        m[subMaxLength] += subMap[subMaxLength]
        if subMaxLength > maxLength {
            maxLength = subMaxLength
        }
    }
    return m[maxLength]
}

[guowei0223]

class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        if len(nums) <= 1:
            return len(nums)
        dp = [1] * len(nums)
        count = [1] * len(nums)
        res = 0
        max_length = 0
        for i in range(1, len(nums)):
            for j in range(0, i):
                if nums[i] > nums[j]:
                    if dp[i] < dp[j] +1:
                        dp[i] = dp[j] + 1
                        count[i] = count[j]
                    elif dp[i] == dp[j] + 1:
                        count[i] += count[j]
            max_length = max(max_length, dp[i])

        for i in range(len(nums)):
            if max_length == dp[i]:
                res += count[i]
        return res

[chenming-cao]

解题思路

动态规划。定义两个数组，len[i]用来储存以nums[i]结尾的LIS的最大长度，count[i]用来储存以nums[i]结尾的最大长度LIS的个数。每次遍历下标在0到i - 1之间的元素nums[j]，如果nums[j]小于当前元素nums[i]，则说明我们可以把nums[i]加到以nums[j]结尾的LIS上形成长度+1的LIS。继续判断，如果len[i] < len[j] + 1说明该以nums[i]结尾的该长度的LIS是第一次出现，将count[i]设成count[j]；如果len[i] == len[j] + 1说明该长度的LIS之前出现过，将count[i]更新加入count[j]。遍历同时不断更新最大长度max。最后遍历len和count数组，将所有长度为max的LIS个数求和即为结果。

代码

class Solution {
    public int findNumberOfLIS(int[] nums) {
        int n = nums.length;
        int[] len = new int[n], count = new int[n]; // length of LIS and total counts of LIS at different index
        int max = 1;
        for (int i = 0; i < n; i++) {
            // initialize arrays, each number can form a LIS of length 1
            len[i] = count[i] = 1;
            for (int j = 0; j < i; j++) {
                // find a LIS which can be formed by appending nums[i]
                if (nums[j] < nums[i]) {
                    if (len[i] < len[j] + 1) { // find the LIS at this length for the first time
                        len[i] = len[j] + 1; // update the length
                        count[i] = count[j]; // update the count of LIS
                    }
                    else if (len[i] == len[j] + 1) { // find another LIS with the same length
                        count[i] += count[j]; // combine the counts
                    }
                }
            }
            max = Math.max(max, len[i]);
        }
        int res = 0;
        // search for LIS with length of max, add up to get the final result
        for (int i = 0; i < n; i++) {
            if (len[i] == max) res += count[i];
        }
        return res;
    }
}

复杂度分析

• 时间复杂度：O(n^2)
• 空间复杂度：O(n)

[GG925407590]

class Solution {
public:
    int findNumberOfLIS(vector<int> &nums) {
        int n = nums.size(), maxLen = 0, ans = 0;
        vector<int> dp(n), cnt(n);
        for (int i = 0; i < n; ++i) {
            dp[i] = 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];
                    }
                }
            }
            if (dp[i] > maxLen) {
                maxLen = dp[i];
                ans = cnt[i]; 
            } else if (dp[i] == maxLen) {
                ans += cnt[i];
            }
        }
        return ans;
    }
};

[mayloveless]

思路

递推公式：dp[i] = 最长的长度的个数,在过程中，补充计数

代码

var findNumberOfLIS = function(nums) {
    const n = nums.length
    const dp = new Array(n).fill(0)
    const cnt = new Array(n).fill(0);
    let res = 0;
    let maxLen = 0;

    for (let i = 0; i < n; ++i) {
        dp[i] = 1;// 代表到目前为止最长的长度
        cnt[i] = 1;// 最长的长度的个数
        for (let 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];// 序列个数一边多，补充计数
                }
            }
        }
        if (dp[i] > maxLen) {
            maxLen = dp[i];
            res = cnt[i];
        } else if (dp[i] === maxLen) {
            res += cnt[i];
        }
    }
    return res;
};

复杂度

时间：O(n^2) 空间：O(n)

[Elsa-zhang]

''' 给定一个未排序的整数数组，找到最长递增子序列的个数。
    dp[i][0]:长度
    dp[i][1]:个数
'''
class Solution:
    def findNumberOfLIS(self, nums: list[int]):
        n = len(nums)
        dp = [[1,1] for i in range(n)]
        longest = 1
        for i in range(n):
            for j in range(i+1, n):
                if nums[j] > nums[i]:
                    if dp[i][0]+1 > dp[j][0]:
                        dp[j][1] = dp[i][1] # 个数
                        dp[j][0] = dp[i][0] + 1 # 长度
                        longest = max(longest, dp[j][0])
                    elif dp[i][0]+1 == dp[j][0]: # 长度一样
                        dp[j][1] += dp[i][1]

        ans = sum(dp[i][1] for i in range(n) if dp[i][0]==longest)
        return ans

[bookyue]

code

    public int findNumberOfLIS(int[] nums) {
        int n = nums.length;
        int[] f = new int[n];
        int[] g = new int[n];
        int max = 1;
        for (int i = 0; i < n; i++) {
            f[i] = g[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    if (f[i] < f[j] + 1) {
                        f[i] = f[j] + 1;
                        g[i] = g[j];
                    } else if (f[i] == f[j] + 1) {
                        g[i] += g[j];
                    }
                }
            }

            max = Math.max(max, f[i]);
        }

        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (f[i] == max) ans += g[i];
        }

        return ans;
    }

[zywang0]

class Solution {
    public int findNumberOfLIS(int[] nums) {
        int n = nums.length, maxLen = 0, ans = 0;
        int[] dp = new int[n];
        int[] cnt = new int[n];
        for (int i = 0; i < n; ++i) {
            dp[i] = 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];
                    }
                }
            }
            if (dp[i] > maxLen) {
                maxLen = dp[i];
                ans = cnt[i]; // 重置计数
            } else if (dp[i] == maxLen) {
                ans += cnt[i];
            }
        }
        return ans;
    }
}

[Dou-Yu-xuan]

class Solution:  
    def findNumberOfLIS(self, nums: List[int]) -> int:  
        if len(nums) <= 1:  
            return len(nums)  
        dp = [1] * len(nums)  
        count = [1] * len(nums)  
        res = 0  
        max_length = 0 
        for i in range(1, len(nums)):  
            for j in range(0, i):  
                if nums[i] > nums[j]: 
                    if dp[i] < dp[j] +1:  
                        dp[i] = dp[j] + 1  
                        count[i] = count[j]  
                    elif dp[i] == dp[j] + 1: 
                        count[i] += count[j] 
            max_length = max(max_length, dp[i]) 

        for i in range(len(nums)):  
             if max_length == dp[i]:  
               res += count[i]  
        return res  

[klspta]

class Solution {
    public int findNumberOfLIS(int[] nums) {
        int n = nums.length;
        if (n <= 1) {
            return n;
        }
        int[] dp = new int[n];
        for(int i = 0; i < dp.length; i++) {
            dp[i] = 1;
        }
        int[] count = new int[n];
        for(int i = 0; i < count.length; i++) {
            count[i] = 1;
        }

        int maxCount = 0;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    if (dp[j] + 1 > dp[i]) {
                        dp[i] = dp[j] + 1;
                        count[i] = count[j];
                    } else if (dp[j] + 1 == dp[i]) {
                        count[i] += count[j];
                    }
                }
                if (dp[i] > maxCount) {
                    maxCount = dp[i];
                }
            }
        }
        int result = 0;
        for (int i = 0; i < n; i++) {
            if (maxCount == dp[i]) {
                result += count[i];
            }
        }
        return result;
    }
}

[chiehw]

思路

用每个数和前面的数对比，如果前面的数小于当前数，那么就尝试更新数组。

更新数组的条件：

• 长度不变：数量+1 就行。
• 长度改变：改变长度，并重置数量。

代码

class Solution {
private:
    void updateNum(int curLen,  int curLenNum, int &len, int &num){
        if (curLen == len) {
            num += curLenNum;
        }
    }

    void resetLenAndNum(int curLen, int curLenNum, int &len, int &num){
        if (curLen > len) {
            len = curLen;
            num = curLenNum; 
        }
    }
public:
    int findNumberOfLIS(vector<int> &nums) {
        int size = nums.size();
        vector<int> lenArr(size, 1), numArr(size, 1);
        int maxLen = 0, maxLenNum = 0;

        for (int endIndex = 0; endIndex < size; ++endIndex) {
            for (int index = 0; index < endIndex; ++index) {
                if (nums[endIndex] > nums[index]) {
                    updateNum(lenArr[index] + 1, numArr[index],  lenArr[endIndex], numArr[endIndex]);
                    resetLenAndNum(lenArr[index] + 1, numArr[index],  lenArr[endIndex], numArr[endIndex]);
                }
            }
            updateNum(lenArr[endIndex], numArr[endIndex], maxLen, maxLenNum);
            resetLenAndNum(lenArr[endIndex], numArr[endIndex], maxLen, maxLenNum);
        }
        return maxLenNum;
    }
};

[RestlessBreeze]

代码

class Solution {
public:
    int findNumberOfLIS(vector<int> &nums) {
        int n = nums.size(), maxLen = 0, ans = 0;
        vector<int> dp(n), cnt(n);
        for (int i = 0; i < n; ++i) {
            dp[i] = 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];
                    }
                }
            }
            if (dp[i] > maxLen) {
                maxLen = dp[i];
                ans = cnt[i]; 
            } else if (dp[i] == maxLen) {
                ans += cnt[i];
            }
        }
        return ans;
    }
};

[paopaohua]

class Solution {
    public int lengthOfLIS(int[] nums) {
       if(nums == null || nums.length == 0){
           return 0;
       } 
       // 定义dp【】
       int length = nums.length;
       int[] dp = new int[length];
       // 初始化整个dp数组全为1 
       Arrays.fill(dp,1);
       int res = 1;
       //遍历
       for(int i = 1; i < length ; i++){
           for(int j = 0 ; j < i;j++){
               if(nums[j] < nums[i]) dp[i] = Math.max(dp[j] + 1,dp[i]);
           }
           res = Math.max(res,dp[i]);
       }
       return res;
    }
}

[MaylingLin]

代码

class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        # dp[i][0] ->  LIS
        # dp[i][1] -> NumberOfLIS
        dp = [[1, 1] for i in range(n)]
        ans = [1, 1]
        longest = 1
        for i in range(n):
            for j in range(i + 1, n):
                if nums[j] > nums[i]:
                    if dp[i][0] + 1 > dp[j][0]:
                        dp[j][0] = dp[i][0] + 1
                        # 下面这行代码容易忘记，导致出错
                        dp[j][1] = dp[i][1]
                        longest = max(longest, dp[j][0])
                    elif dp[i][0] + 1 == dp[j][0]:
                        dp[j][1] += dp[i][1]
        return sum(dp[i][1] for i in range(n) if dp[i][0] == longest)

复杂度

---

• Time: $O(N^2)$，令N为数组长度。
• Space: $O(N)$

[BruceZhang-utf-8]

代码

• 语言支持：Java

Java Code:

class Solution {
    public int findNumberOfLIS(int[] nums) {
        int n = nums.length;
        if(n == 1) return 1;

        int[] dp = new int[n];
        int[] count = new int[n];
        Arrays.fill(dp, 1);
        Arrays.fill(count, 1);
        int maxLength = 0;

        for(int i = 1; i < n; i++){
            for(int j = 0; j < i; j++){
                if(nums[i] > nums[j]){
                    if(dp[j] + 1 > dp[i]){
                        dp[i] = dp[j] + 1;
                        count[i] = count[j];
                    }else if(dp[j] + 1 == dp[i]){
                        count[i] += count[j];
                    }
                }
            }
            maxLength = Math.max(maxLength, dp[i]);
        }

        int res = 0;
        for(int i = 0; i < n; i++){
            if(dp[i] == maxLength){
                res += count[i];
            }
        }
        return res;
    }
}

[tiandao043]

思路

dp[i][0] 表示 以 nums[i] 结尾的最长上升子序列的长度，dp[i][1] 表示 以 nums[i] 结尾的长度为 dp[i][0] 的子序列的个数

代码

class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        int n=nums.size();
        vector<int> dp1(n+1,1);
        vector<int> dp2(n+1,1);
        int longmax=1;
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                if(nums[j]>nums[i]){
                    if(dp1[i]+1>dp1[j]){

                        dp1[j]=dp1[i]+1;
                        dp2[j]=dp2[i];
                        longmax=max(longmax,dp1[j]);
                    }else if(dp1[i]+1==dp1[j]){
                        dp2[j]+=dp2[i];
                    }
                }
            }
        }
        int ans=0;
        // cout<<longmax<<endl;
        for(int i=0;i<n;i++){
            // cout<<dp1[i]<<endl;
            if(dp1[i]==longmax){
                ans+=dp2[i];

            }
        }
        return ans;
    }
};

O(n^2) O(n)

[Jetery]

代码 (java)

class Solution {
    public int findNumberOfLIS(int[] nums) {
        int n = nums.length;
        int[] f = new int[n], g = new int[n];
        int max = 1;
        for (int i = 0; i < n; i++) {
            f[i] = g[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    if (f[i] < f[j] + 1) {
                        f[i] = f[j] + 1;
                        g[i] = g[j];
                    } else if (f[i] == f[j] + 1) {
                        g[i] += g[j];
                    }
                }
            }
            max = Math.max(max, f[i]);
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (f[i] == max) ans += g[i];
        }
        return ans;
    }
}

[AtaraxyAdong]

class Solution {
    public int findNumberOfLIS(int[] nums) {
        int length = nums.length;
        int maxLength = 1;
        int res = 0;
        // dp[i][0] 表示 以 nums[i] 结尾的最长上升子序列的长度
        // dp[i][1] 表示 以 nums[i] 结尾的长度为 dp[i][0] 的子序列的个数。
        // 最长递增子序列的长度最少为 1

        int[][] dp = new int[length][2];
        for (int i = 0; i < length; i++) {
            Arrays.fill(dp[i], 1);
        }

        for (int i = 0; i < length; i++) {
            for (int j = i + 1; j < length; j++) {
                // 可以拼接
                if (nums[j] > nums[i]) {
                    // 在 j 处拼接后，判断序列是否变长了
                    if (dp[i][0] + 1 > dp[j][0]) {
                        // 以 nums[j] 结尾的最长上升子序列长度，在前面的基础 +1
                        dp[j][0] = dp[i][0] + 1;
                        dp[j][1] = dp[i][1];
                        maxLength = Math.max(maxLength, dp[j][0]);
                    } else if (dp[i][0] + 1 == dp[j][0]) {
                        dp[j][1] += dp[i][1];
                    }
                }
            }
        }
        for (int i = 0; i < length; i++) {
            if (dp[i][0] == maxLength) {
                res += dp[i][1];
            }
        }
        return res;
    }
}

[Ryanbaiyansong]

class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        f = [1] * n 
        cnt = [1] * n 
        longest = 1
        for i in range(1, n):
            for j in range(i):
                if nums[j] < nums[i]:
                    cur = f[j] + 1
                    if cur > f[i]:
                        f[i] = cur
                        cnt[i] = cnt[j]
                    elif cur == f[i]:
                        cnt[i] += cnt[j]
            longest = max(longest, f[i])

    #    #  print(longest)
    #     print(cnt)
    #     print(f)
        ans = 0
        for i in range(n):
            if f[i] == longest:
                ans += cnt[i]

        return ans