Given an integer array nums, return the number of longest increasing subsequences.
Notice that the sequence has to be strictly increasing.
Example 1:
Input: nums = [1,3,5,4,7]
Output: 2
Explanation: The two longest increasing subsequences are [1, 3, 4, 7] and [1, 3, 5, 7].
Example 2:
Input: nums = [2,2,2,2,2]
Output: 5
Explanation: The length of the longest increasing subsequence is 1, and there are 5 increasing subsequences of length 1, so output 5.
Constraints:
1 <= nums.length <= 2000
-106 <= nums[i] <= 106
The answer is guaranteed to fit inside a 32-bit integer.
Solutions
Solution 1: Dynamic Programming
Thinking
We need both the LIS length and how many such sequences exist. \(n\le 2000\) allows \(O(n^2)\).
\(f[i]\) and \(\textit{cnt}[i]\) are the best length and count ending at \(i\). Update or add when \(\textit{nums}[j]<\textit{nums}[i]\). Sum \(\textit{cnt}\) over positions that attain the global maximum length.
We define \(f[i]\) as the length of the longest increasing subsequence ending with \(\textit{nums}[i]\), and \(\textit{cnt}[i]\) as the number of longest increasing subsequences ending with \(\textit{nums}[i]\). Initially, \(f[i]=1\), \(\textit{cnt}[i]=1\). Also, we define \(mx\) as the length of the longest increasing subsequence, and \(\textit{ans}\) as the number of longest increasing subsequences.
For each \(\textit{nums}[i]\), we enumerate all elements \(\textit{nums}[j]\) in \(\textit{nums}[0:i-1]\). If \(\textit{nums}[j] < \textit{nums}[i]\), then \(\textit{nums}[i]\) can be appended after \(\textit{nums}[j]\) to form a longer increasing subsequence. If \(f[i] < f[j] + 1\), it means the length of the longest increasing subsequence ending with \(\textit{nums}[i]\) has increased, so we need to update \(f[i]=f[j]+1\) and \(\textit{cnt}[i]=\textit{cnt}[j]\). If \(f[i]=f[j]+1\), it means we have found a longest increasing subsequence with the same length as before, so we need to increase \(\textit{cnt}[i]\) by \(\textit{cnt}[j]\). Then, if \(mx < f[i]\), it means the length of the longest increasing subsequence has increased, so we need to update \(mx=f[i]\) and \(\textit{ans}=\textit{cnt}[i]\). If \(mx=f[i]\), it means we have found a longest increasing subsequence with the same length as before, so we need to increase \(\textit{ans}\) by \(\textit{cnt}[i]\).
Finally, we return \(\textit{ans}\).
The time complexity is \(O(n^2)\), and the space complexity is \(O(n)\), where \(n\) is the length of the array \(\textit{nums}\).
Scanning all previous indices is the bottleneck. After compressing values, a Fenwick tree stores the best length and count among smaller keys, so each step is \(O(\log n)\).
We can use a binary indexed tree to maintain the length and count of the longest increasing subsequence in the prefix interval. We remove duplicates from the array \(\textit{nums}\) and sort it to get the array \(\textit{arr}\). Then we enumerate each element \(x\) in \(\textit{nums}\), find the position \(i\) of \(x\) in the array \(\textit{arr}\) by binary search, then query the length and count of the longest increasing subsequence in \([1,i-1]\), denoted as \(v\) and \(\textit{cnt}\), then update the length and count of the longest increasing subsequence in \([i]\) to \(v+1\) and \(\max(\textit{cnt},1)\). Finally, we query the length and count of the longest increasing subsequence in \([1,m]\), where \(m\) is the length of the array \(\textit{arr}\), which is the answer.
The time complexity is \(O(n \log n)\), and the space complexity is \(O(n)\), where \(n\) is the length of the array \(\textit{nums}\).