Number of Longest Increasing Subsequence

LeetCode Q 673 - Number of Longest Increasing Subsequence

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.

Similar Question: Longest Increasing Subsequence

Solution :

1. State:

   • len[i], record the longest increasing subsequence till ith num in nums. The length of len should be the nums.length.
   • count[i], the number of the string whose length is i. The length of len should be the nums.length.

2. state transfer fuction:
   len[i] = Math.max(len[j] + 1, len[i]), where j = 1,…,i-1 and nums[i] > nums[j].

Note then when building array len, we should also update the array count.
- if (len[i] < len[j] + 1) then count[i] = count[j];
- if (len[i] == len[j] + 1) then count[i] += count[j];

3. boundary cases: dp[i] = count[i] = 1

Time Complexity: O(n^2)
Space Complexity: O(n)

Code:

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

	int[] len = new int[nums.length];
	int[] count = new int[nums.length];
	
	int res = 0, maxLen = 0;
	for (int i = 0; i < nums.length; i++) {
		len[i] = count[i] = 1;
		// update len[i] and count[i] 
		for (int j = 0; j < i ; j++) {
			if (nums[i] > nums[j]) {
				if (len[i] == len[j] + 1) {
					count[i] += count[j];
				}
				if (len[i] < len[j] + 1) {
					len[i] = len[j] + 1;
					count[i] = count[j];
				}
			}
		}
		// update maxLen
		if (maxLen == len[i]) {
			res += count[i];
		}
		if (maxLen < len[i]) {
			maxLen = len[i];
			res = count[i];
		}
	}

	return res;
}