最长递增子序列
leetcode 300 最长递增子序列
leetcode 673 最长递增子序列的个数
对于673题，常规做法动态规划，记录两个状态 最长上升子序列的长度与当前长度对应的子序列的个数。动态规划的规划过程
$$
arr[j] > arr[i] \
if; dp[j] < dp[i] + 1 \quad dp[j] = dp[i] + 1, nums[j] = nums[i] \
else ;if ; dp[j] == dp[i] + 1 \quad nums[j] += nums[i]
$$
动态规划规划的复杂度为$O(n^2)$
采用树状数组$O(nlogn)$的复杂度，定义Node结构体，记录长度与个数，重载加法操作符。
维护小于等于当前值区间的最长长度的上升子序列个数。
1
2
3
4
5
6
7
8
9
10
11
12
13
| struct Node {
int m, c;
Node (int _m, int _c) : m(_m), c(_c) {}
Node& operator +=(Node &rhs) {
if (m < rhs.m) {
m = rhs.m;
c = rhs.c;
} else if (m == rhs.m) {
c += rhs.c;
}
return *this;
}
};
|
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
| class Solution {
public:
int findNumberOfLIS(vector<int>& nums) {
vector<int> arr = nums;
sort(arr.begin(), arr.end());
arr.erase(unique(arr.begin(), arr.end()), arr.end());
unordered_map<int, int> mp;
for (int i = 0; i < arr.size(); ++i) {
mp[arr[i]] = i + 1;
}
vector<Node> tree(2010, {0, 0});
Node res(0, 0);
for (int val : nums) {
Node tmp(0, 1);
for (int k = mp[val] - 1; k > 0; k -= (k & -k)) {
tmp += tree[k];
}
tmp.m++;
res += tmp;
for (int k = mp[val]; k < 2010; k += (k & -k)) {
tree[k] += tmp;
}
}
return res.c;
}
};
|