题目

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

分析

这道题给定一个整数数组，找到最长的递增序列的个数。是Longest Continuous Increasing Subsequence的升级版，只是找最长递增序列时，没有连续的限制，看来这种没有连续限制的题经常出，需要注意。
方法是动态规划，建立两个数组，分别是len[i]表示第i位最长递增序列的长度和cnt[i]表示第i位上最长递增序列的数量。

1. 每次刚到达第i位时，将len[i]和cnt[i]都置为1表示只考虑第i位这一个数。
2. 扫描第i位之前的数字nums[j]，如果nums[i]>nums[j]，则表示nums[i]可以加在nums[j]最长序列的后面构成一3个新的序列。
3. 再对这个新的序列长度和已经找到的i上的最长序列长度加以判断，新的序列的长度是len[j] + 1

• 如果len[i] == len[j] + 1，则表示在找到j之前已经有加上nums[i]构成序列且长度与这次新的序列长度相同，二者的cnt可以累加。
• 如果len[i] < len[j] + 1，则表示新的序列时目前找到的到i为止最长的序列，则将len[i]和cnt[i]更新为len[j] + 1和cnt[j]。
• 如果len[i] > len[j]+1，则表示新的序列不如之前已经找到的序列长，就不用考虑了。

这种跳跃的情况应该记录下到某一个位置为止时的状态，这属于动态规划的前向思想。

代码

public int findNumberOfLIS(int[] nums) {
    if(nums.length <= 1) return nums.length;
    int[] len = new int[nums.length];
    int[] cnt = new int[nums.length];
    int res = 0, max_len = 0;
    
    for(int i = 0; i < nums.length; ++i){
        len[i] = cnt[i] = 1;  //长度为1，计数为1
        for(int j = 0; j < i; ++j){
            if(nums[i] > nums[j]){  //递增
                if(len[i] == len[j] + 1){
                    cnt[i] += cnt[j];
                }else if(len[i] < len[j] + 1){
                    len[i] = len[j] + 1;
                    cnt[i] = cnt[j];
                }
            }
        }
        
        if(max_len == len[i]) res += cnt[i];
        else if(max_len < len[i]){
            max_len = len[i];
            res = cnt[i];
        }
    }
    
    return res;
}