1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
|
// 673. Number of Longest Increasing Subsequence
#include "leetcode.h"
/*
* given an integer array 'nums', return the number of longest increasing
* subsequences. notice that the sequence has to strictly increasing.
*/
class Solution {
public:
int findNumberOfLIS(vector<int> &nums) {
if (nums.empty())
return 0;
vector<vector<pair<int, int>>> dyn(nums.size() + 1);
int curr_max = 0;
for (int i = 0; i < nums.size(); ++i) {
int l = 0, r = curr_max;
while (l < r) {
int mid = l + (r - l) / 2;
if (dyn[mid].back().first < nums[i])
l = mid + 1;
else
r = mid;
}
int options = 1, 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 : dyn[row][l1 - 1].second;
}
dyn[l].push_back(
{nums[i],
(dyn[l].empty() ? options : dyn[l].back().second + options)});
if (l == curr_max)
curr_max++;
}
return dyn[curr_max - 1].back().second;
}
};
int main() {
Solution obj;
vector<int> n1 = {1, 3, 5, 4, 7}, n2 = {2, 2, 2, 2, 2};
printf("%d\n", obj.findNumberOfLIS(n1)); // expect: 2
printf("%d\n", obj.findNumberOfLIS(n2)); // expect: 5
}
|