题目描述

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

示例 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位有符号整数。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/number-of-longest-increasing-subsequence
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解法1 – Top-down

这道题目是第300题的升级,那道题目仅要求找出最长递增子序列(LIS)的长度,而这道题目需要统计LIS有多少个。为了求出数组nums的LIS个数,我们先要求得最长递增子序列的长度maxLen。然后扫描nums数组,统计LIS长度为maxLen的个数。

首先我们实现一个函数,求数组nums的LIS的长度(参考300题的Top-down解法)。我们定义函数lengthOfLIS(int[] nums, int n),表示计算数组nums前n个元素(n从1开始,包含第n个且必须使用第n个元素)能够形成LIS的长度。例如我们有nums = [1,2,3,2,2],那么lengthOfLIS(nums, 4) = 2而不是3,因为我们必须使用nums[4]。

为了求num前n个元素的LIS,我们可以使用递归来解决。对于长度n,我们向前寻找某一元素i,使其满足nums[n] > nums[i](递增的定义),然后递归调用lengthOfLIS(nums, i),即求解nums数组前i个元素的LIS。代码如下:

private int lengthOfLIS(int[] nums, int n) {
    int maxLen = 1;
    for (int i = 0; i < n; i++) {
        if (nums[n-1] > nums[i-1]) {
            maxLen = Math.max(maxLen, lengthOfLIS(nums, i) + 1);
        }
    }
    return maxLen;
}

下一步,我们定义函数count(int[] nums, int n)用于计算nums前n个元素(n从1开始,包含第n个且必须使用第n个元素)构成的LIS长度为maxLen的递增子序列数量。它会调用上面实现的函数lengthOfLIS(nums, n)。在这里我们举一个例子,nums = [1,3,2,4,5],则

count(nums, 1) = 1,因为前1个元素为[1],maxLen = lengthOfLIS(nums, 1) = 1,只能找到1个长度为1的LIS:[1].

count(nums, 2) = 1, 因为前2个元素为[1,3],maxLen = lengthOfLIS(nums, 2) = 2,只能找到1个长度为2的LIS:[1,3]

count(nums, 3) = 1, 因为前3个元素为[1,3,2],maxLen = lengthOfLIS(nums, 3) = 2,只能找到1个长度为2的LIS:[1,2]。你可能会疑问,为什么[1,3]不计算在内?因为前面说过,count(nums, n)的定义是必须使用第n个元素,即num[3 – 1] = 2。

count(nums, 4) = 2,因为前4个元素为[1,3,2,4],maxLen = lengthOfLIS(nums, 4) = 3,能找到2个长度为3的LIS:[1,3,4]和[1,2,4]。

count(nums, 5) = 2,因为前5个元素为[1,3,2,4,5],maxLen = lengthOfLIS(nums, 5) = 4,能找到2个长度为4的LIS:[1,3,4,5]和[1,2,4,5]。

下面,我们看一下count(nums, n)是如何实现的:

public int count(int[] nums, int n) {
    int c = 0;
    int maxLen = lengthOfLIS(nums, n);
    for (int i = 1; i <= n; i++) {
        if (nums[n - 1] > nums[i - 1] && lengthOfLIS(nums, i) + 1 == maxLen) {
            c += count(nums, i);
        }
    }
    return c == 0 ? 1 : c;
}

我们首先从n的前面的寻找位置i,查看是否存在num[i] < nums[n](递增定义)。如果找到这样的i,我们计算lengthOfLIS(nums, i) + 1是否与maxLen相等(lengthOfLIS(nums, i) + 1表示将第n个元素接续到子序列后面)。如果找到这样的位置i,我们调用c += count(nums, i)统计有多少个LIS的长度为maxLen – 1。最后,如果找不到长度为maxLen – 1的子序列就返回1。这表示该LIS自己成为独立的一个子序列,例如nums = [4,3,2,1],很明显每一个元素的前面都找不到比他小的元素,所以每个元素自己独立成为一个LIS。

最后,我们将count和lengthOfLIS组合起来调用,就能求得问题的答案:最长LIS的个数。

public int findNumberOfLIS(int[] nums) {
    int maxLen = 0;
    // 先求得整个数组nums的LIS的长度maxLen
    for (int i = 1; i <= nums.length; i++)
        maxLen = Math.max(maxLen, lengthOfLIS(nums, i));
    // 统计长度为maxLen的数量
    int ans = 0;
    for (int i = 1; i <= nums.length; i++) {
        if (lengthOfLIS(nums, i) == maxLen) {
            ans += count(nums, i);
        }
    }
    return ans;
}

到这里我们就实现了Top-down解法,但是这个实现并不能AC。因为使用递归会造成重复求解相同的子问题,当问题的规模扩大后运行时间会相当长。我们可以使用len[|nums| + 1]来存储函数lengthOfLIS计算过的解;使用另一个数组count[|nums| + 1]来存储函数count计算过的解。全部代码如下:

class Solution {
    private int[] len;
    private int[] count;

    public int findNumberOfLIS(int[] nums) {
        int maxLen = 0;
        len = new int[nums.length + 1];
        count = new int[nums.length + 1];
        for (int i = 1; i <= nums.length; i++)
            maxLen = Math.max(maxLen, lengthOfLIS(nums, i));
        int ans = 0;
        for (int i = 1; i <= nums.length; i++) {
            if (lengthOfLIS(nums, i) == maxLen) {
                ans += count(nums, i);
            }
        }
        return ans;
    }

    private int lengthOfLIS(int[] nums, int n) {
        if (len[n] > 0)
            return len[n];
        int maxLen = 1;
        for (int i = 1; i <= n; i++) {
            if (nums[n - 1] > nums[i - 1]) {
                maxLen = Math.max(maxLen, lengthOfLIS(nums, i) + 1);
            }
        }

        len[n] = maxLen;
        return maxLen;
    }

    public int count(int[] nums, int n) {
        if (count[n] > 0)
            return count[n];
        int c = 0;
        int maxLen = lengthOfLIS(nums, n);
        for (int i = 1; i <= n; i++) {
            if (nums[n - 1] > nums[i - 1] && lengthOfLIS(nums, i) + 1 == maxLen) {
                c += count(nums, i);
            }
        }
        if (c == 0)
            c = 1;
        count[n] = c;
        return c;
    }
}

解法2 – Bottom-up

我们定义数组dp[|nums| + 1],dp[n]表示对于nums的前n个元素(n > 0,包含第n个且必须使用第n个元素)形成的LIS长度。dp数组开始时所有元素都为1,表示每个元素都是一个LIS,之后我们会把每个LIS拼接起来成为更长的LIS。

定义数组count[|nums| + 1],count[n]表示对于nums的前n个元素形成的长度为dp[n]的LIS的数量。count数组初始值也所有元素都为1。

简而言之dp用来存放LIS长度,count用来存放该长度下LIS的数量。接下来我们怎样更新数组dp和count呢?

if (nums[i - 1] > nums[j - 1]) {
    if (dp[j] >= dp[i]) { // 分支1
        dp[i] = dp[j] + 1;
        count[i] = count[j];
    } else if (dp[j] + 1 == dp[i]) { // 分支2
        count[i] += count[j];
    }
}

我们来举一个例子,nums = [1,3,2,4,5];初始时dp = [1,1,1,1,1];count = [1,1,1,1,1];i = 1~|nums|, 1 <= j < i。

分支1:

     LIS: [1], LIS: [3] -> LIS: [1, 3]

当i = 2, j = 1时,nums[1] > nums[0]成立,dp[1] == dp[2],更新dp[2] = dp[1] + 1,count[2] = count[1]。物理意义是:在i的前面找到了一个以nums[j – 1]结尾的LIS,将nums[i]接到这个子序列后面形成更长的LIS。所以执行dp[i] = dp[j] + 1,表示多了一个元素num[i – 1];执行count[i] = count[j],因为拼接后形成的只是一个更长的子序列,LIS的数量和count[j]一致。

分支2

    
     LIS: [1, 3]-\                 [1, 3, 4]        (1)
                  \LIS: [4] -> LIS: 
                  /                [1, 2, 4]        (2)
     LIS: [1, 2]-/
     

(1)当i = 4,j = 2时, dp[j] = 2, count[j] = 1;nums[3] > nums[1],且dp[2] > dp[4]成立,更新dp[4] = dp[2] + 1 = 3,count[4] = count[2] = 1。形成新的LIS = [1, 3, 4]。

(2)当i = 4,j = 3时,dp[j] = 2,count[j] = 1;nums[3] > nums[2],成立且dp[3] + 1 == dp[4]。那么我们执行count[4] += count[3],此时我们找到了两个LIS = [1, 3, 4]和[1, 2, 4]。

全部代码如下:

class Solution {
    public int findNumberOfLIS(int[] nums) {
        int[] dp = new int[nums.length + 1];
        int[] count = new int[nums.length + 1];
        int maxLIS = 1;
        Arrays.fill(dp, 1);
        Arrays.fill(count, 1);
        
        for (int i = 1; i <= nums.length; i++) {
            for (int j = 1; j < i; j++) {
                if (nums[i - 1] > nums[j - 1]) {
                    if (dp[j] >= dp[i]) {
                        dp[i] = dp[j] + 1;
                        count[i] = count[j];
                    } else if (dp[j] + 1 == dp[i]) {
                        count[i] += count[j];
                    }
                }
            }
            maxLIS = Math.max(maxLIS, dp[i]);
        }
        int ans = 0;
        for (int i = 1; i <= nums.length; i++) {
            if (dp[i] == maxLIS) {
                ans += count[i];
            }
        }
        return ans;
    }
}

Leave a Reply

Your email address will not be published. Required fields are marked *