题目描述

Given an unsorted array of integers, find the number of longest increasing subsequence.

样例

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].


Example 2:
Input: [2,2,2,2,2]
Output: 5


Explanation: The length of longest continuous increasing subsequence is 1, and there are 5 subsequences' length is 1, so output 5.

Note: Length of the given array will be not exceed 2000 and the answer is guaranteed to be fit in 32-bit signed int.

算法

(动态规划) O(n^2)

由类似LeetCode300+数据范围基本确认是dp题目，做法类似300，但新加一个数组times表示记录以i为结尾的子序列里面包含的最长上升子序列出现的组合出现次数。times[i]的数字只和dp[j] + 1 和 dp[i]之间的大小关系确定，具体看我代码注释的思路。

Java 代码

public class Solution {

    public int findNumberOfLIS(int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }

        // dp(i) 记录以i为结尾的子序列里面包含的最长上升子序列的数字个数
        // d(i) = max{1, d(j)+1},其中j<i,A[j]<=A[i], 初始值1
        int[] dp = new int[n];

        // times(i) 记录以i为结尾的子序列里面包含的最长上升子序列出现的组合出现次数
        int[] times = new int[n];
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
            times[i] = 1;
        }

        int maxLen = 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] <= nums[j]) {
                    continue;
                }

                // 找到更长的了
                if (dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                    // 这个可以这么理解：当[...j]形成的组合数是值是times[j]的话，其每一种组合结尾补上[i],即[...j,i],对于组合数本身是没有增加的，还是原本times值，唯独只是递增子序列的长度+1了
                    times[i] = times[j];
                } else if (dp[j] + 1 == dp[i]) {
                    // 找到一个一样长的了
                    // 现在的组合次数+counter[j]的组合次数
                    times[i] += times[j];
                }
            }
            maxLen = Math.max(maxLen, dp[i]);
        }

        int res = 0;
        for (int i = 0; i < n; i++) {
            if (dp[i] == maxLen) {
                res += times[i];
            }
        }

        return res;
    }

}