673. Number of Longest Increasing Subsequence

Problem:

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.

Analysis:

Again similar to Longest Increasing Subsequence. Beside the length dp array, we need another dp array to keep record of the count of LIS til i. 

For example, the array [1,2,3,4,5,4,7,2]. The LIS length is 5. 

If we reach nums[i] == 7, nums[j] == 5.

LIS ends with 5 are [1,2,4,5],  [1,2,3,5]

Append 7 to them, LIS ends with 7 are [1,2,4,5,7], [1,2,3,5,7]

The count of LIS ends with 7 and 5 are the same. 

We continue to 4 after 5, LIS end with 4 is [1, 2, 3, 4]. Append 7 we got [1,2,3,4,7], but the count becomes 3.

还有个方法是用segment tree做。segment tree性价比超低，代码量特别大，适应性又很小。那个什么alex wice长得太丑了根本不想看他写的东西。

Solution:

被leetcode 高票答案坑死了。他不用if和else if,这样的话两个if block必须排好序。如果像我下面这样写，每一次都要经过 == 的情况。实际上判断顺序完全无所谓。所谓的高手也就那样吧。

class Solution {
    public int findNumberOfLIS(int[] nums) {
        if (nums == null || nums.length == 0)
            return 0;
        
        int len = nums.length;
        int[] maxLength = new int[len];
        int[] maxCount = new int[len];
        Arrays.fill(maxLength, 1);
        Arrays.fill(maxCount, 1);
        int res = 0;
        int maxLen = 0;
        
        for (int i = 0; i < len; i++) {
            for (int  j= 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    // first time increase length
                    if (maxLength[i] < maxLength[j] + 1) {
                        maxLength[i] = maxLength[j] + 1;
                        maxCount[i] = maxCount[j];
                    } 
                    // no increase, need to add length of new subsequences
                    else if (maxLength[i] == maxLength[j] + 1) {
                        maxCount[i] += maxCount[j];
                    }
                }
            }
            
            if (maxLength[i] == maxLen) {
                res += maxCount[i];
            } else if (maxLength[i] > maxLen) {
                res = maxCount[i];
                maxLen = maxLength[i];
            }
        }
        return res;
    }
}