https://leetcode.com/problems/number-of-longest-increasing-subsequence/description/
X. http://guoyc.com/post/num_of_lis/
http://www.cnblogs.com/grandyang/p/7603903.html
https://zxi.mytechroad.com/blog/dynamic-programming/leetcode-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.
X. http://guoyc.com/post/num_of_lis/
从上面的O(n^2)的解法来看，也是可以计算出LIS的长度的，而在LeetCode 300. Longest Increasing Subsequence我们用另一个动态规划的方式，再加上二分查找，可以在O(n logn)的时间复杂度内得到LIS的长度。现在就是对这个解法进行扩充，让它能够同时保存LIS的个数。
LeetCode 300中，我们每一个dp[i]保存的是长度为i的LIS结尾元素的最小值。也就是说，之前的LIS结尾元素信息都被覆盖了，而统计LIS个数是需要这些信息的，那么就不能直接覆盖最小值，可以把dp[i]变成一个数组，发生更新时在数组末尾加上新值。那么每一个dp[i]中保存着一些nums中的数字，并且这些数字呈递减。现在我们在dp[i]为每一个数字再加上一个值，是这个数字作为长度为i的递增子序列最后一个元素的LIS的个数，所以dp[i]是一个数组，数组中每一个元素是[num, count(num)]。
有了这样的数据结构，对于nums中每一个num，我们先用二分查找找到它的位置idx，然后把idx-1中所有小于它的元素的count加到一起作为num的count值。那么这样做的复杂度是O(len(dp[i]))，即最坏情况是N，每一个元素进行O(N)的操作会导致复杂度还是O(N^2)。这里可以使用累积的方式来避免重复求和，即每一个[num, count]对中的count是它以及前面每个数的LIS数目之和。这样要计算idx-1中小于它元素的count之和只需要二分查找到小于num的元素x，用总count减去[x, count_x]中的count_x即得到num作为最后一个元素的LIS数目。
代码如下：
| |
时间花了1100+ms，不符合复杂度，原因是用bisect来进行二分搜索的时候，每一次都新建了一个数组，而这个复杂度是O(N)的，所以时间并没有减少。而bisect的查找并不支持自定义key。所以只能自己写了：
| |
只花了92ms,击败100%。回顾一下，这里对于每一个元素进行了两次二分查找，第一次在dp数组中，第二次在dp[i]数组中，都是O(logN)，所以总复杂度为O(n logn)
https://leetcode.com/problems/number-of-longest-increasing-subsequence/discuss/107295/9ms-C%2B%2B-Explanation%3A-DP-%2B-Binary-search-%2B-prefix-sums-O(NlogN)-time-O(N)-space
The idea is to modify classic LIS solution which uses binary search to find the "insertion point" of a currently processed value. At
These values are held in the first part of the pairs in
If we want to know how many options do we have to end a LIS of length
That is the basic idea, the running time is O(NlogN), because we just do 2 binary searches for every element of the input. Space complexity is O(N), as every element of the input will be contained in the
Feel free to post any corrections or simpler explanations :)
dyn[k] we don't store a single number representing the smallest value such that there exists a LIS of length k+1 as in classic LIS solution. Instead, at dyn[k] we store all such values that were once endings of a k+1 LIS (so we keep the history as well).These values are held in the first part of the pairs in
vector<pair<int,int>> which we get by indexing dyn vector. So for example in a pair x = {a, b} the first part -- a, indicates that there exists a LIS of length k+1 such that it ends with a value a. The second part -- b, represents the number of possible options for which LIS of length k+1ends with a value equal to or greater than a. This is the place where we use prefix sums.If we want to know how many options do we have to end a LIS of length
m with value y, we just binary search for the index i of a pair with first part strictly less than y in dyn[m-2]. Then the number of options is dyn[m-2].back().second - dyn[m-2][i-1].second or just dyn[m-2].back() if i is 0.That is the basic idea, the running time is O(NlogN), because we just do 2 binary searches for every element of the input. Space complexity is O(N), as every element of the input will be contained in the
dyn vector exactly once.Feel free to post any corrections or simpler explanations :)
class Solution {
public:
int findNumberOfLIS(vector<int>& nums) {
if (nums.empty())
return 0;
vector<vector<pair<int, int>>> dyn(nums.size() + 1);
int max_so_far = 0;
for (int i = 0; i < nums.size(); ++i) {
// bsearch insertion point
int l = 0, r = max_so_far;
while (l < r) {
int mid = l + (r - l) / 2;
if (dyn[mid].back().first < nums[i]) {
l = mid + 1;
} else {
r = mid;
}
}
// bsearch number of options
int options = 1;
int row = l - 1;
if (row >= 0) {
int l1 = 0, r1 = dyn[row].size();
while (l1 < r1) {
int mid = l1 + (r1 - l1) / 2;
if (dyn[row][mid].first < nums[i]) {
r1 = mid;
} else {
l1 = mid + 1;
}
}
options = dyn[row].back().second;
options -= (l1 == 0) ? 0 : dyn[row][l1 - 1].second;
}
dyn[l].push_back({nums[i], (dyn[l].empty() ? options : dyn[l].back().second + options)});
if (l == max_so_far) {
max_so_far++;
}
}
return dyn[max_so_far-1].back().second;
}
我们用两个数组length和count来记录在每一个位置，LIS的长度与个数。如：nums[:i+1]中LIS的长度与个数分别为length[i]和count[i]
那么递推的公式就是：
i处LIS的长度取决于i之前比i小的元素的length
length[i] = max(length[j]+1) for j in range(0, i) if nums[j]<nums[i]
i处LIS的个数取决于i之前比i小的元素的长度为length[i]-1的LIS的个数
count[i] = sum(count[j]) for j in range(0, i) if lenght[j]==length[i]-1
代码如下：
| |
1400+ms，只击败了17%的Solution，那么在这个解法的基础上，其实还是可以改进的，我们对[0:i]进行了两次循环可以改成一次：
| |
700+ms, 击败70ms的Solution。
这道题给了我们一个数组，让我们求最长递增序列的个数，题目中的两个例子也很好的说明了问题。那么对于这种求个数的问题，直觉告诉我们应该要使用DP来做。其实这道题在设计DP数组的时候有个坑，如果我们将dp[i]定义为到i位置的最长子序列的个数的话，那么递推公式不好找。但是如果我们将dp[i]定义为以nums[i]为结尾的递推序列的个数的话，再配上这些递推序列的长度，将会比较容易的发现递推关系。
这里我们用len[i]表示以nums[i]为结尾的递推序列的长度，用cnt[i]表示以nums[i]为结尾的递推序列的个数，初始化都赋值为1，只要有数字，那么至少都是1。然后我们遍历数组，对于每个遍历到的数字nums[i]，我们再遍历其之前的所有数字nums[j]，当nums[i]小于等于nums[j]时，不做任何处理，因为不是递增序列。反之，则判断len[i]和len[j]的关系，如果len[i]等于len[j] + 1，说明nums[i]这个数字可以加在以nums[j]结尾的递增序列后面，并且以nums[j]结尾的递增序列个数可以直接加到以nums[i]结尾的递增序列个数上。如果len[i]小于len[j] + 1，说明我们找到了一条长度更长的递增序列，那么我们此时奖len[i]更新为len[j]+1，并且原本的递增序列都不能用了，直接用cnt[j]来代替。我们在更新完len[i]和cnt[i]之后，要更新mx和res，如果mx等于len[i]，则把cnt[i]加到res之上；如果mx小于len[i]，则更新mx为len[i]，更新结果res为cnt[i]
这里我们用len[i]表示以nums[i]为结尾的递推序列的长度，用cnt[i]表示以nums[i]为结尾的递推序列的个数，初始化都赋值为1，只要有数字，那么至少都是1。然后我们遍历数组，对于每个遍历到的数字nums[i]，我们再遍历其之前的所有数字nums[j]，当nums[i]小于等于nums[j]时，不做任何处理，因为不是递增序列。反之，则判断len[i]和len[j]的关系，如果len[i]等于len[j] + 1，说明nums[i]这个数字可以加在以nums[j]结尾的递增序列后面，并且以nums[j]结尾的递增序列个数可以直接加到以nums[i]结尾的递增序列个数上。如果len[i]小于len[j] + 1，说明我们找到了一条长度更长的递增序列，那么我们此时奖len[i]更新为len[j]+1，并且原本的递增序列都不能用了，直接用cnt[j]来代替。我们在更新完len[i]和cnt[i]之后，要更新mx和res，如果mx等于len[i]，则把cnt[i]加到res之上；如果mx小于len[i]，则更新mx为len[i]，更新结果res为cnt[i]
https://leetcode.com/problems/number-of-longest-increasing-subsequence/discuss/107293/JavaC++-Simple-dp-solution-with-explanation
The idea is to use two arrays
len[n] and cnt[n] to record the maximum length of Increasing Subsequence and the coresponding number of these sequence which ends with nums[i], respectively. That is:len[i]: the length of the Longest Increasing Subsequence which ends with nums[i].cnt[i]: the number of the Longest Increasing Subsequence which ends with nums[i].
Then, the result is the sum of each
cnt[i] while its corresponding len[i] is the maximum length.
Java version:
public int findNumberOfLIS(int[] nums) {
int n = nums.length, res = 0, max_len = 0;
int[] len = new int[n], cnt = new int[n];
for(int i = 0; i<n; i++){
len[i] = cnt[i] = 1;
for(int j = 0; j <i ; j++){
if(nums[i] > nums[j]){
if(len[i] == len[j] + 1)cnt[i] += cnt[j];
if(len[i] < len[j] + 1){
len[i] = len[j] + 1;
cnt[i] = cnt[j];
}
}
}
if(max_len == len[i])res += cnt[i];
if(max_len < len[i]){
max_len = len[i];
res = cnt[i];
}
}
return res;
}
Suppose for sequences ending at
nums[i], we knew the length length[i] of the longest sequence, and the number count[i] of such sequences with that length.
For every
i < j with A[i] < A[j], we might append A[j] to a longest subsequence ending at A[i]. It means that we have demonstrated count[i] subsequences of length length[i] + 1.
Now, if those sequences are longer than
length[j], then we know we have count[i] sequences of this length. If these sequences are equal in length to length[j], then we know that there are now count[i]additional sequences to be counted of that length (ie. count[j] += count[i]).public int findNumberOfLIS(int[] nums) { int N = nums.length; if (N <= 1) return N; int[] lengths = new int[N]; //lengths[i] = length of longest ending in nums[i] int[] counts = new int[N]; //count[i] = number of longest ending in nums[i] Arrays.fill(counts, 1); for (int j = 0; j < N; ++j) { for (int i = 0; i < j; ++i) if (nums[i] < nums[j]) { if (lengths[i] >= lengths[j]) { lengths[j] = lengths[i] + 1; counts[j] = counts[i]; } else if (lengths[i] + 1 == lengths[j]) { counts[j] += counts[i]; } } } int longest = 0, ans = 0; for (int length: lengths) { longest = Math.max(longest, length); } for (int i = 0; i < N; ++i) { if (lengths[i] == longest) { ans += counts[i]; } } return ans; }
len[i]: the length of the Longest Increasing Subsequence which ends with nums[i].cnt[i]: the number of the Longest Increasing Subsequence which ends with nums[i].public int findNumberOfLIS(int[] nums) {
int n = nums.length, res = 0, max_len = 0;
int[] len = new int[n], cnt = new int[n];
for(int i = 0; i<n; i++){
len[i] = cnt[i] = 1;
for(int j = 0; j <i ; j++){
if(nums[i] > nums[j]){
if(len[i] == len[j] + 1)cnt[i] += cnt[j];
if(len[i] < len[j] + 1){
len[i] = len[j] + 1;
cnt[i] = cnt[j];
}
}
}
if(max_len == len[i])res += cnt[i];
if(max_len < len[i]){
max_len = len[i];
res = cnt[i];
}
}
return res;
}
X. Segment Tree
Suppose we knew for each length
L, the number of sequences with length L ending in x. Then when considering the next element of nums, updating our knowledge hinges on knowing the number of sequences with length L-1 ending in y < x. This type of query over an interval is a natural fit for using some sort of tree.
We could try using Fenwick trees, but we would have to store of them, which naively might be space. Here, we focus on an implementation of a Segment Tree.
Algorithm
Implementing Segment Trees is discussed in more detail here. In this approach, we will attempt a variant of segment tree that doesn't use lazy propagation.
First, let us call the "value" of an interval, the longest length of an increasing subsequence, and the number of such subsequences in that interval.
Each node knows about the interval of
nums values it is considering [node.range_left, node.range_right], and it knows about node.val, which contains information on the value of interval. Nodes also have node.left and node.right children that represents the left and right half of the interval node considers. These child nodes are created on demand as appropriate.
Now,
query(node, key) will tell us the value of the interval specified by node, except we'll exclude anything above key. When key is outside the interval specified by node, we return the answer. Otherwise, we'll divide the interval into two and query both intervals, then merge the result.
What does
merge(v1, v2) do? Suppose two nodes specify adjacent intervals, and have corresponding values v1 = node1.val, v2 = node2.val. What should the aggregate value, v = merge(v1, v2) be? If there are longer subsequences in one node, then v will just be that. If both nodes have longest subsequences of equal length, then we should count subsequences in both nodes. Note that we did not have to consider cases where larger subsequences were made, since these were handled by insert.
What does
insert(node, key, val) do? We repeatedly insert the key into the correct half of the interval that node specifies (possibly a point), and after such insertion this node's value could change, so we merge the values together again.
Finally, in our main algorithm, for each
num in nums we query for the value length, count of the interval below num, and we know it will lead to count additional sequences of length length + 1. We then update our tree with that knowledge.- Time Complexity: where is the length of
nums. In our main for loop, we do$$O(\log{N})$$work toqueryandinsert. - Space Complexity: , the space used by the segment tree.
public Value merge(Value v1, Value v2) { if (v1.length == v2.length) { if (v1.length == 0) return new Value(0, 1); return new Value(v1.length, v1.count + v2.count); } return v1.length > v2.length ? v1 : v2; } public void insert(Node node, int key, Value val) { if (node.range_left == node.range_right) { node.val = merge(val, node.val); return; } else if (key <= node.getRangeMid()) { insert(node.getLeft(), key, val); } else { insert(node.getRight(), key, val); } node.val = merge(node.getLeft().val, node.getRight().val); } public Value query(Node node, int key) { if (node.range_right <= key) return node.val; else if (node.range_left > key) return new Value(0, 1); else return merge(query(node.getLeft(), key), query(node.getRight(), key)); } public int findNumberOfLIS(int[] nums) { if (nums.length == 0) return 0; int min = nums[0], max = nums[0]; for (int num: nums) { min = Math.min(min, num); max = Math.max(max, num); } Node root = new Node(min, max); for (int num: nums) { Value v = query(root, num-1); insert(root, num, new Value(v.length + 1, v.count)); } return root.val.count; } } class Node { int range_left, range_right; Node left, right; Value val; public Node(int start, int end) { range_left = start; range_right = end; left = null; right = null; val = new Value(0, 1); } public int getRangeMid() { return range_left + (range_right - range_left) / 2; } public Node getLeft() { if (left == null) left = new Node(range_left, getRangeMid()); return left; } public Node getRight() { if (right == null) right = new Node(getRangeMid() + 1, range_right); return right; } class Value { int length; int count; public Value(int len, int ct) { length = len; count = ct; } }
https://zxi.mytechroad.com/blog/dynamic-programming/leetcode-673-number-of-longest-increasing-subsequence/
int findNumberOfLIS(vector<int>& nums) {
int n = nums.size();
if (n == 0) return 0;
c_ = vector<int>(n, 0);
l_ = vector<int>(n, 0);
// Find the length LIS.
int max_len = 0;
for (int i = 0; i < n; ++i)
max_len = max(max_len, len(nums, i));
// Checking all endings.
int ans = 0;
for (int i = 0; i < n; ++i)
if (len(nums, i) == max_len)
ans += count(nums, i);
return ans;
}
private:
vector<int> c_; // c[i]: number of LIS ends with nums[i] / NLIS'
vector<int> l_; // l[i]: lengeh of LIS ends with nums[i] / LIS'
// Number of LIS ends with nums[n]
int count(const vector<int>& nums, int n) {
if (n == 0) return 1;
if (c_[n] > 0) return c_[n];
int total_count = 0;
int l = len(nums, n);
for (int i = 0; i < n; ++i)
if (nums[n] > nums[i] && len(nums, i) == l-1)
total_count += count(nums, i);
if (total_count == 0)
total_count = 1;
return c_[n] = total_count;
}
// Length of LIS ends with nums[n]
int len(const vector<int>& nums, int n) {
if (n == 0) return 1;
if (l_[n] > 0) return l_[n];
int max_len = 1;
// Check every subarray
for (int i = 0; i < n; ++i)
if (nums[n] > nums[i])
max_len = max(max_len, len(nums, i) + 1);
return l_[n] = max_len;
}
