LeetCode 673. Number of Longest Increasing Subsequence

Problem

LeetCode 673. Number of Longest Increasing Subsequence

1. 题目简述

给出一个未排序的整形数组，返回其最长递增系序列的数量。例如：

Example 1:
Input: [1,3,5,4,7]
Output: 2
Explanation: The two longest increasing subsequence are [1, 3, 4, 7] and [1, 3, 5, 7].

Note:

数据规模不会超过2000且保证最终的解是32位整形数

2. 算法思路

相关问题：

1. LeetCode 300. Longest Increasing Subsequence

和300题不同的是，这里我们需要返回的是数量，而不是长度，也就是说仅仅找出长度已经无法满足我们的需求，我们不仅需要记录长度，还需要记录数量。

另一种思路是使用segement tree，暂时还没学到那块，等学到了在回头看！！！

动态规划

我们需要记录的有两个数值，到当前数字截止的最长的递增子序列长度和数量。因此，这是一个二维dp问题。对于300题中的第二种解法我们可以抛弃了，因为它只能找出长度，而无法找到数量。

因此，我们记录一个二维dp数组，每一维数组都有两个值，一个是长度，一个是数量。

当我们向前一个个查找的时候，记录最长的递增子序列的数量。

时间复杂度为O(n ^ 2)，因为每次都要去找前面所有的数字，很慢。

class Solution {
    public int findNumberOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        // dp[i][0]表示到当前的最长长度，dp[i][1]表示当前最长长度的数量；初始化dp[0][0] = 0, dp[0][1] = 1。
        int n = nums.length;
        int[][] dp = new int [n][2];
        for (int i = 0; i < n; i++) {
            dp[i][0] = 1;
        }
        dp[0][1] = 1;

        int maxLength = 1;
        for (int i = 1; i < n; i++) {
            // 这里需要注意！！！count需要初始化为1，因为假设说前面都没有比它小的，那么它就不会进入循环，它自己本身就是一个序列。
            int count = 1, longestLength = 1;
            for (int j = 0; j < i; j++) {
                // 只有当前面数字比当前数字小的时候才会进行判断
                if (nums[j] < nums[i]) {
                    if (longestLength < dp[j][0] + 1) {
                        count = dp[j][1];
                        longestLength = dp[j][0] + 1;
                    } else if (longestLength == dp[j][0] + 1) {
                        count += dp[j][1];
                    }
                }
            }
            dp[i][0] = longestLength;
            dp[i][1] = count;
            maxLength = Math.max(maxLength, longestLength);
        }

        // 根据最长长度遍历dp数组，记录总的最长长度数量
        int res = 0;
        for (int i = 0; i < n; i++) {
            if (dp[i][0] == maxLength) {
                res += dp[i][1];
            }
        }

        return res;
    }
}