Number of Longest Increase Subsequence

Posted on | Edited on | In | | Views:

678. Number of Longest Increasing Subsequence

Given a unsorted array of intergers, find the 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. 最长字串是什么
  2. 有多少个这样长度的最长字串

所以, 一开始, 我们要建立两个数组, most_len 和 count. most_len

  • most_len[k] 表示以nums[k]为结尾的最长递增子串的长度.
  • count[k] 表示以nums[k]为结尾的最长递增子串的个数.

对于每一个nums[l], 遍历nums[0]到nums[i-1], 找到比nums[i]小且长度最长的nums[k], 就可以得出以nums[i]为末尾的最长递增子串的长度. 同时,
以nums[i]结尾的最长递增子串的个数应该等于nums[j]中, 比nums[j]小且长度最长的所有nums[k]的最长递增子串的个数的和

说了一段这么绕的话, 要理解, 需要实际例子来帮助.

nums = [1, 3, 5, 4, 7]
首先要初始化两个数组, 用来记录长度和个数.

most_len = [1, 1, 1, 1, 1]
count = [1, 1, 1, 1, 1]

然后从$i=1$开始遍历:

  • nums[i] = 3, 比3小只有1, 所以 most_len[i] = most_len[0]+1 = 2, count[i] = count[0] = 1
  • nums[i] = 5, 比5小且最长的是3, 所以most_len[i] = most_len[1]+1 = 3, count[i] = count[1] = 1
  • nums[i] = 4, 比4小且最长的是3, 所以most_len[i] = most_len[1]+1=3, count[i] = count[1] = 1
  • nums[i] = 7, 比7小最最长的是5和4, 所以most_len[i] = most_len[2]+1=4, count[i] = count[2] + count[3] = 2

遍历完后, 结果是most_len = [1, 2, 3, 3, 4], count = [1, 1, 1, 1, 2]

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def findNumberOfLIS(nums):
    most_len = [1] * len(nums)
    count = most_len
    maxLen = 1
    i = 0
    res = 0

    for i in range(1, len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                if most_len[j] + 1 > most_len[i]:
                    most_len[i] = most_len[j] + 1
                    count[i] = count[j]
                elif most_len[j] + 1 == most_len[i]:
                    count[i] += count[j]
        maxLen = max(maxLen, most_len[i])
    
    for i in range(len(nums)):
        if maxLen == most_len[i]:
            res += count[i]
    return res

复杂度

$O(n^2)$, $n$为输入数组的长度

EOF