【Day 56 】2023-04-10 - 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位有符号整数。

[JiangyanLiNEU]

class Solution:
  def findNumberOfLIS(self, nums: List[int]) -> int:
    dp = [1] * len(nums)
    count = [1] * len(nums)
    for i in range(len(nums)):
        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]
    max_len = max(dp)
    return sum([count[i] for i in range(len(nums)) if dp[i] == max_len])

[lp1506947671]

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)

杂度分析

令 N 为数组长度。

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

[Abby-xu]

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

        return sum([j for i,j in zip(dp,cnt) if i == max_val])

[LIMBO42]

class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        // 以nums[i]为结尾的子序列的长度
        vector<int> dp(nums.size(), 1);
        vector<int> ans(nums.size(), 1);
        int max_num = 1;
        for(int i = 0; i < nums.size(); ++i) {
            for(int j = 0; j < i; ++j) {
                if(nums[i] > nums[j]) {
                    if(dp[i] == dp[j] + 1) {
                        ans[i] += ans[j];
                    } else if(dp[i] < dp[j] + 1){
                        dp[i] = dp[j] + 1;
                        ans[i] = ans[j];
                    }
                }
            }

            max_num = max(max_num, dp[i]);
        }

        int count = 0;
        for(int i = 0; i < nums.size(); ++i) {
            if(max_num == dp[i]) {
                count += ans[i];
            }
        }
        return count;

    }
};

[jackgaoyuan]

func findNumberOfLIS(nums []int) int {
    type info struct {
        maxLen int //最大递增子序列长度
        cnt int    //最大递增子序列个数
    }
    var dp [2000]info
    for i:=0; i<len(nums); i++ { //初始化，长度为1，个数为1
        dp[i] = info{1, 1}
    }

    for i:=0; i<len(nums); i++ {
        for j:=i-1; j>=0; j-- {
            if nums[i] > nums[j] { //当第i数大于第j数的值时
                if 1+dp[j].maxLen > dp[i].maxLen { //当第j数的最大递增子序列长度+1 大于 当前第i数的最大长度
                    dp[i].maxLen = 1+dp[j].maxLen //更新第i数的最大长度
                    dp[i].cnt = dp[j].cnt //更新第i数的最大长度个数
                } else if 1+dp[j].maxLen == dp[i].maxLen { //当第j数的最大递增子序列长度+1 等于 当前第i数的最大长度
                     dp[i].cnt += dp[j].cnt //则累加个数
                }
            }
        }
    }

    maxLen, cnt := 0, 0 //数组內最大递增子序列长度和个数
    for i:=0; i<len(nums); i++ {
        if dp[i].maxLen > maxLen { //大于
            maxLen = dp[i].maxLen //更新长度
            cnt = dp[i].cnt //更新个数
        } else if dp[i].maxLen == maxLen { //等于
            cnt += dp[i].cnt //累加个数
        }
    }
    return cnt
}

[SoSo1105]

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

    return sum([j for i,j in zip(dp,cnt) if i == max_val])

[xb798298436]

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)

[NorthSeacoder]

var findNumberOfLIS = function(nums) {
    const len = new Array(nums.length).fill(1);//len[i]=>nums[i]结尾的最长子序列长度
    const dp = new Array(nums.length).fill(1);//dp[i]=>nums[i]结尾的最长子序列个数
    //dp[i] = max(dp[0,i-1 while(num[j]<nums[i-1])])+1
    for (let i = 1; i < nums.length; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                if (len[j] + 1 > len[i]) {
                    len[i] = len[j] + 1;
                    dp[i] = dp[j]
                } else if (len[j] + 1 === len[i]) {
                    dp[i] += dp[j]
                }
            }
        }
    }
    const maxLen = Math.max(...len);
    let res = 0
    len.forEach((val, i) => {
        if (val === maxLen) {
            res += dp[i]
        }
    })
    return res
};

[GuitarYs]

var findNumberOfLIS = function(nums) { const len = new Array(nums.length).fill(1);//len[i]=>nums[i]结尾的最长子序列长度 const dp = new Array(nums.length).fill(1);//dp[i]=>nums[i]结尾的最长子序列个数 //dp[i] = max(dp[0,i-1 while(num[j]<nums[i-1])])+1 for (let i = 1; i < nums.length; i++) { for (let j = 0; j < i; j++) { if (nums[j] < nums[i]) { if (len[j] + 1 > len[i]) { len[i] = len[j] + 1; dp[i] = dp[j] } else if (len[j] + 1 === len[i]) { dp[i] += dp[j] } } } } const maxLen = Math.max(...len); let res = 0 len.forEach((val, i) => { if (val === maxLen) { res += dp[i] } }) return res };

[chanceyliu]

代码

function findNumberOfLIS(nums: number[]): number {
  let n = nums.length,
    maxLen = 0,
    ans = 0;
  const dp = new Array(n).fill(0);
  const cnt = new Array(n).fill(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];
      ans = cnt[i]; // 重置计数
    } else if (dp[i] === maxLen) {
      ans += cnt[i];
    }
  }
  return ans;
}

复杂度分析

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

[Meisgithub]

class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> dp(n, vector<int>(2, 1));
        int maxLen = 1;
        int count = 1;
        for (int i = 1; i < n; ++i)
        {
            for (int j = 0; j < i; ++j)
            {
                if (nums[j] < nums[i])
                {
                    if (dp[j][0] + 1 == dp[i][0])
                    {
                        dp[i][1] += dp[j][1];
                    }
                    if (dp[j][0] + 1 > dp[i][0])
                    {
                        dp[i][1] = dp[j][1];
                    }
                    dp[i][0] = max(dp[i][0], dp[j][0] + 1);
                }
            }
            if (dp[i][0] == maxLen)
            {
                count += dp[i][1];
            }
            if (dp[i][0] > maxLen)
            {
                maxLen = dp[i][0];
                count = dp[i][1];
            }

        }

        return count;
    }
};

[aswrise]

class Solution(object):
    def findNumberOfLIS(self, nums):
        N = len(nums)
        if N <= 1: return N
        lengths = [0] * N #lengths[i] = longest ending in nums[i]
        counts = [1] * N #count[i] = number of longest ending in nums[i]

        for j, num in enumerate(nums):
            for i in xrange(j):
                if nums[i] < nums[j]:
                    if lengths[i] >= lengths[j]:
                        lengths[j] = 1 + lengths[i]
                        counts[j] = counts[i]
                    elif lengths[i] + 1 == lengths[j]:
                        counts[j] += counts[i]

        longest = max(lengths)
        return sum(c for i, c in enumerate(counts) if lengths[i] == longest)

[RestlessBreeze]

code

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

[sye9286]

思路

代码

var findNumberOfLIS = function(nums) {
    let n = nums.length, maxLen = 0, ans = 0;
    const dp = new Array(n).fill(0);
    const cnt = new Array(n).fill(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];
            ans = cnt[i]; 
        } else if (dp[i] === maxLen) {
            ans += cnt[i];
        }
    }
    return ans;
};

复杂度分析

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

[FireHaoSky]

思路：动态规划，在进行数组大小比较的同时，进行计数操作，然后一遍遍的更新长度

代码：python

class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        max_len = 0
        ans = 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

复杂度分析：

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

[harperz24]

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

        dp = [[1, 1] for _ in range(n)] 
        # [length, count]
        # length: 以 nums[i] 结尾的最长递增子序列的长度
        # count: 以 nums[i] 结尾的最长递增子序列的个数
        max_length = 1  # 最长递增子序列的长度

        for i in range(1, n):
            for j in range(i):
                if nums[j] < nums[i]:
                    # 如果长度更长，则更新
                    if dp[j][0] + 1 > dp[i][0]:
                        dp[i][0] = dp[j][0] + 1
                        dp[i][1] = dp[j][1]
                    # 如果长度相等，则累加个数
                    elif dp[j][0] + 1 == dp[i][0]:
                        dp[i][1] += dp[j][1]
            # 更新最长递增子序列长度
            max_length = max(max_length, dp[i][0])

        res = 0
        for k in range(n):
            if dp[k][0] == max_length:
                res += dp[k][1]
        return res

[linlizzz]

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

        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)

T(n) = O(n^2)

S(n) = O(n)

[CruiseYuGH]

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

    return sum([j for i,j in zip(dp,cnt) if i == max_val])

[Diana21170648]

思路

动态规划

代码

class Slution:
    def findnumsofLIS(self,nums:list[int]) -> int:
        n=len(nums)
        #dp[i][0]存储最长上升子序列的长度
        #dp[i][1]存储最长上升子序列的个数
        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)

**复杂度分析**
- 时间复杂度：O(N^2)，其中 N 为数组长度。
- 空间复杂度：O(N)

[jmaStella]

public int findNumberOfLIS(int[] nums) {
    int maxLen = 0;
    // length of longest LIS
    int[] len = new int[nums.length];
    // count
    int[] count = new int[nums.length];
    int result =0;
    for(int i=0; i<nums.length; i++){
        len[i] = 1;
        count[i] = 1;
        for(int j=0; j<i; j++){
            if(nums[i] > nums[j]){
                if(len[i] == len[j]+1){
                    System.out.println(i +" "+ j);
                    count[i] += count[j];
                }
                if(len[i] < len[j]+1){
                    len[i] = len[j]+1;
                    count[i] = count[j];
                }

            }
        }
        if(maxLen == len[i]){
            result+=count[i];
        }
        if(maxLen < len[i]){
            maxLen = len[i];
            result = count[i];
        }
    }
    System.out.println(Arrays.toString(len));
    System.out.println(Arrays.toString(count));
    return result;

}

[kofzhang]

思路

动态规划，记录两个值，分别是以当前值结尾的最长长度和以当前值结尾的数量

复杂度

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

代码

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

[Size-of]

var findNumberOfLIS = function(nums) { let n = nums.length, maxLen = 0, ans = 0; const dp = new Array(n).fill(0); const cnt = new Array(n).fill(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]; ans = cnt[i]; } else if (dp[i] === maxLen) { ans += cnt[i]; } } return ans; };

[Hughlin07]

public int findNumberOfLIS(int[] nums) {

    int n = nums.length, res = 0, max_len = 0;
    int[] len =  new int[n], cnt = new int[n];
    for(int i = 0; i<n; i++){
        len[i] = cnt[i] = 1;
        for(int j = 0; j <i ; j++){
            if(nums[i] > nums[j]){
                if(len[i] == len[j] + 1)cnt[i] += cnt[j];
                if(len[i] < len[j] + 1){
                    len[i] = len[j] + 1;
                    cnt[i] = cnt[j];
                }
            }
        }
        if(max_len == len[i])res += cnt[i];
        if(max_len < len[i]){
            max_len = len[i];
            res = cnt[i];
        }
    }
    return res;

}

[wangqianqian202301]

代码

class Solution:
    def findNumberOfLIS(self, nums):
        if not nums: return 0

        decks, ends_decks, paths = [], [], []
        for num in nums:
            deck_idx = bisect.bisect_left(ends_decks, num)
            n_paths = 1
            if deck_idx > 0:
                l = bisect.bisect(decks[deck_idx-1], -num)
                n_paths = paths[deck_idx-1][-1] - paths[deck_idx-1][l]

            if deck_idx == len(decks):
                decks.append([-num])
                ends_decks.append(num)
                paths.append([0,n_paths])
            else:
                decks[deck_idx].append(-num)
                ends_decks[deck_idx] = num
                paths[deck_idx].append(n_paths + paths[deck_idx][-1])

        return paths[-1][-1]

[JingYuZhou123]

/**
 * @param {number[]} nums
 * @return {number}
 */
var findNumberOfLIS = function(nums) {
    let n = nums.length, maxLen = 0, ans = 0;
    const dp = new Array(n).fill(0);
    const cnt = new Array(n).fill(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];
            ans = cnt[i]; // 重置计数
        } else if (dp[i] === maxLen) {
            ans += cnt[i];
        }
    }
    return ans;
};

[wangzh0114]

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;
    }
};

[KrabbeJing]

class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 0: return 0
        if n == 1: return 1
        longest = 1
        dp = [[1,1] for i in range(n)]
        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)

[kangliqi1]

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)

[bookyue]

TC: O(n^2)
SC: O(n)

    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;
    }

[zhangyu1131]

class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        // 直接求个数不好求，因为最长递增子序列的长度都没确定
        // 那就先求最长递增子序列的长度，再求最大长度的过程中可以累计这个最长长度是由哪些前置来完成的，就可以记录出个数
        if (nums.empty())
        {
            return 0;
        }
        int n = nums.size();
        vector<int> dp(n + 1, 0); // dp[i]表示以i结尾的最长递增子序列长度
        vector<int> cpy_nums(1, INT_MIN);
        vector<int> max_cnt_dp(n + 1, 0); // max_cnt_dp[i]表示以i结尾的最大递增子序列的种数
        max_cnt_dp[0] = 1;
        for (auto num : nums)
        {
            cpy_nums.push_back(num);
        }
        // 递推
        int total_max_length = 0;
        for (int i = 1; i <= n; ++i)
        {
            int max_length = 0;
            int max_length_cnt = 0;
            for (int j = 0; j < i; ++j)
            {
                if (cpy_nums[i] <= cpy_nums[j]) // 未构成一个升序
                {
                    continue;
                }
                // 升序
                int tmp = dp[j] + 1;// dp[i]至少有这个长度
                if (tmp > max_length) // 最大长度超过已有的
                {
                    max_length = tmp;
                    max_length_cnt = max_cnt_dp[j];
                    total_max_length = std::max(total_max_length, max_length);
                    dp[i] = tmp;
                }
                else if (tmp == max_length)
                {
                    max_length_cnt += max_cnt_dp[j];
                }
            }
            max_cnt_dp[i] = max_length_cnt;
        }

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

[Lydia61]

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

思路

动态规划

代码

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

复杂度分析

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

[X1AOX1A]

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)

[Fuku-L]

代码

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;
    }
}

复杂度分析

• 时间复杂度：O(N^2)，其中 N 为数组长度。
• 空间复杂度：O(N)

[AstrKing]

代码

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;
    }
}

[yingchehu]

class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        dp =  [[1, 1] for i in range(n)] # [最長長度, 最長長度的個數]

        for i in range(n):
            for j in range(i):
                if nums[i] > nums[j]:
                    if dp[j][0] + 1 > dp[i][0]: # 若長度更長，更新最長長度與個數
                        dp[i][0] = dp[j][0] + 1
                        dp[i][1] = dp[j][1]
                    elif dp[j][0] + 1 == dp[i][0]: # 若長度一樣，累加個數
                        dp[i][1] += dp[j][1]
        longest = max([dp[i][0] for i in range(n)])
        return sum([dp[i][1] for i in range(n) if dp[i][0] == longest])

[joemonkeylee]

思路

贪心 + 前缀和 + 二分查找 没做出来。mark

代码

     public int FindNumberOfLIS(int[] nums) {
        IList<IList<int>> d = new List<IList<int>>();
        IList<IList<int>> cnt = new List<IList<int>>();
        foreach (int v in nums) {
            int i = BinarySearch1(d.Count, d, v);
            int c = 1;
            if (i > 0) {
                int k = BinarySearch2(d[i - 1].Count, d[i - 1], v);
                c = cnt[i - 1][cnt[i - 1].Count - 1] - cnt[i - 1][k];
            }
            if (i == d.Count) {
                IList<int> dIList = new List<int>();
                dIList.Add(v);
                d.Add(dIList);
                IList<int> cntIList = new List<int>();
                cntIList.Add(0);
                cntIList.Add(c);
                cnt.Add(cntIList);
            } else {
                d[i].Add(v);
                int cntSize = cnt[i].Count;
                cnt[i].Add(cnt[i][cntSize - 1] + c);
            }
        }

        int count1 = cnt.Count, count2 = cnt[count1 - 1].Count;
        return cnt[count1 - 1][count2 - 1];
    }

    public int BinarySearch1(int n, IList<IList<int>> d, int target) {
        int l = 0, r = n;
        while (l < r) {
            int mid = (l + r) / 2;
            IList<int> list = d[mid];
            if (list[list.Count - 1] >= target) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }

    public int BinarySearch2(int n, IList<int> list, int target) {
        int l = 0, r = n;
        while (l < r) {
            int mid = (l + r) / 2;
            if (list[mid] < target) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }

复杂度分析

• 时间复杂度：O(nlogn)
• 空间复杂度：O(1)

[enrilwang]

class Solution { public: int findNumberOfLIS(vector& nums) { // 以nums[i]为结尾的子序列的长度 vector dp(nums.size(), 1); vector ans(nums.size(), 1); int max_num = 1; for(int i = 0; i < nums.size(); ++i) { for(int j = 0; j < i; ++j) { if(nums[i] > nums[j]) { if(dp[i] == dp[j] + 1) { ans[i] += ans[j]; } else if(dp[i] < dp[j] + 1){ dp[i] = dp[j] + 1; ans[i] = ans[j]; } } }

        max_num = max(max_num, dp[i]);
    }

    int count = 0;
    for(int i = 0; i < nums.size(); ++i) {
        if(max_num == dp[i]) {
            count += ans[i];
        }
    }
    return count;

}

};

[Jetery]

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;
    }
}

[snmyj]

class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
       int n=nums.size(),maxlen=0;
       vector<int> dp(n,0);

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

           maxlen=max(dp[i],maxlen);
       }
       return maxlen;
    }
};

[tzuikuo]

思路

动态规划

代码

class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        int n=nums.size(),maxcount=1,re=0;
        vector<vector<int>> dp(n,vector<int>(2,0));
        cout<<1<<" ";
        dp[0][0]=1;
        dp[0][1]=1;
        for(int i=1;i<n;i++){
            dp[i][0]=1;
            for(int j=0;j<i;j++){
                if(nums[i]>nums[j]) dp[i][0]=max(dp[i][0],dp[j][0]+1);
            }
            if(dp[i][0]>maxcount) maxcount=dp[i][0];
            cout<<dp[i][0]<<" ";
        }
        cout<<endl;
        cout<<1<<" ";
        for(int i=1;i<n;i++){
            for(int j=0;j<i;j++){
                if(dp[j][0]==dp[i][0]-1&&nums[j]<nums[i]) dp[i][1]+=dp[j][1];
                if(dp[i][0]==1) dp[i][1]=1;
            }
            cout<<dp[i][1]<<" ";
        }
        for(int i=0;i<n;i++){
            if(dp[i][0]==maxcount) re+=dp[i][1];
        }
        return re;
    }
};

复杂度分析

• 时间复杂度：O(N)
• 空间复杂度：O(N)

[JasonQiu]

import bisect
class Solution(object):
    def findNumberOfLIS(self, nums):
        dp = []
        tree = defaultdict(list)
        for i in nums:
            index = bisect.bisect_left(dp, i)
            if idx == len(dp):
                dp.append(i)
            else:
                dp[index] = i
            total = 0
            for counter, last_num in tree[index]:
                if last_num < i:
                    total += counter
            tree[index + 1].append((max(1, total), i))
        return sum(i[0] for i in tree[len(tree) - 1])

[Zoeyzyzyzy]

class Solution {
    // 利用之前300题计算最大长度的方法计算出最大长度，
    // count[i]为已nums[i]为结尾的字符串最长递增子序列的个数
    // 再遍历一遍dp[i]，把最长递增序列长度对应的count[i]累计下来就是结果了。
    // Time Complexity: O(n^2) Space Complexity:O(n^2)
    public int findNumberOfLIS(int[] nums) {
        int n = nums.length;
        if (n == 1)
            return n;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        int[] count = new int[n];
        Arrays.fill(count, 1);
        int maxCount = 1;
        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]) {
                        count[i] = count[j];
                    } else if (dp[j] + 1 == dp[i]) {
                        count[i] += count[j];
                    }
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
                if (dp[i] > maxCount)
                    maxCount = dp[i];
            }
        }
        int res = 0;
        for (int i = 0; i < n; i++) {
            if (maxCount == dp[i])
                res += count[i];
        }
        return res;
    }