class Solution {
public:
int findNumberOfLIS(vector<int>& nums) {
}
};
673. 最长递增子序列的个数
给定一个未排序的整数数组 nums ， 返回最长递增子序列的个数 。
注意 这个数列必须是 严格 递增的。
示例 1:
输入: [1,3,5,4,7] 输出: 2 解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。
示例 2:
输入: [2,2,2,2,2] 输出: 5 解释: 最长递增子序列的长度是1，并且存在5个子序列的长度为1，因此输出5。
提示:
1 <= nums.length <= 2000-106 <= nums[i] <= 106原站题解
golang 解法, 执行用时: 16 ms, 内存消耗: 3.5 MB, 提交时间: 2023-09-27 10:40:34
// 二分搜索
func findNumberOfLIS2(nums []int) int {
d := [][]int{}
cnt := [][]int{}
for _, v := range nums {
i := sort.Search(len(d), func(i int) bool { return d[i][len(d[i])-1] >= v })
c := 1
if i > 0 {
k := sort.Search(len(d[i-1]), func(k int) bool { return d[i-1][k] < v })
c = cnt[i-1][len(cnt[i-1])-1] - cnt[i-1][k]
}
if i == len(d) {
d = append(d, []int{v})
cnt = append(cnt, []int{0, c})
} else {
d[i] = append(d[i], v)
cnt[i] = append(cnt[i], cnt[i][len(cnt[i])-1]+c)
}
}
c := cnt[len(cnt)-1]
return c[len(c)-1]
}
// dp
func findNumberOfLIS(nums []int) (ans int) {
maxLen := 0
n := len(nums)
dp := make([]int, n)
cnt := make([]int, n)
for i, x := range nums {
dp[i] = 1
cnt[i] = 1
for j, y := range nums[:i] {
if x > y {
if dp[j]+1 > dp[i] {
dp[i] = dp[j] + 1
cnt[i] = cnt[j] // 重置计数
} else if dp[j]+1 == dp[i] {
cnt[i] += cnt[j]
}
}
}
if dp[i] > maxLen {
maxLen = dp[i]
ans = cnt[i] // 重置计数
} else if dp[i] == maxLen {
ans += cnt[i]
}
}
return
}
javascript 解法, 执行用时: 76 ms, 内存消耗: 44.5 MB, 提交时间: 2023-09-27 10:39:53
/**
* @param {number[]} nums
* @return {number}
*/
var findNumberOfLIS_dp = function(nums) {
let n = nums.length, maxLen = 0, ans = 0;
const dp = new Array(n).fill(0);
const cnt = new Array(n).fill(0);
for (let i = 0; i < n; ++i) {
dp[i] = 1;
cnt[i] = 1;
for (let j = 0; j < i; ++j) {
if (nums[i] > nums[j]) {
if (dp[j] + 1 > dp[i]) {
dp[i] = dp[j] + 1;
cnt[i] = cnt[j]; // 重置计数
} else if (dp[j] + 1 === dp[i]) {
cnt[i] += cnt[j];
}
}
}
if (dp[i] > maxLen) {
maxLen = dp[i];
ans = cnt[i]; // 重置计数
} else if (dp[i] === maxLen) {
ans += cnt[i];
}
}
return ans;
};
/**
* @param {number[]} nums
* @return {number}
*/
// 二分搜索
var findNumberOfLIS = function(nums) {
const d = [];
const cnt = [];
for (const v of nums) {
const i = binarySearch1(d.length, d, v);
let c = 1;
if (i > 0) {
const k = binarySearch2(d[i - 1].length, d[i - 1], v);
c = cnt[i - 1][cnt[i - 1].length - 1] - cnt[i - 1][k];
// console.log(cnt, i)
}
if (i === d.length) {
const dList = [];
dList.push(v);
d.push(dList);
const cntList = [];
cntList.push(0);
cntList.push(c);
cnt.push(cntList);
} else {
d[i].push(v);
const cntSize = cnt[i].length;
cnt[i].push(cnt[i][cntSize - 1] + c);
}
}
const size1 = cnt.length, size2 = cnt[size1 - 1].length;
return cnt[size1 - 1][size2 - 1];
}
const binarySearch1 = (n, d, target) => {
let l = 0, r = n;
while (l < r) {
const mid = Math.floor((l + r) / 2);
const list = d[mid];
if (list[list.length - 1] >= target) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
}
const binarySearch2 = (n, list, target) => {
let l = 0, r = n;
while (l < r) {
const mid = Math.floor((l + r) / 2);
if (list[mid] < target) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
}
java 解法, 执行用时: 22 ms, 内存消耗: 41.8 MB, 提交时间: 2023-09-27 10:39:04
class Solution {
// dp
public int findNumberOfLIS(int[] nums) {
int n = nums.length, maxLen = 0, ans = 0;
int[] dp = new int[n];
int[] cnt = new int[n];
for (int i = 0; i < n; ++i) {
dp[i] = 1;
cnt[i] = 1;
for (int j = 0; j < i; ++j) {
if (nums[i] > nums[j]) {
if (dp[j] + 1 > dp[i]) {
dp[i] = dp[j] + 1;
cnt[i] = cnt[j]; // 重置计数
} else if (dp[j] + 1 == dp[i]) {
cnt[i] += cnt[j];
}
}
}
if (dp[i] > maxLen) {
maxLen = dp[i];
ans = cnt[i]; // 重置计数
} else if (dp[i] == maxLen) {
ans += cnt[i];
}
}
return ans;
}
// 二分搜索
public int findNumberOfLIS2(int[] nums) {
List<List<Integer>> d = new ArrayList<List<Integer>>();
List<List<Integer>> cnt = new ArrayList<List<Integer>>();
for (int v : nums) {
int i = binarySearch1(d.size(), d, v);
int c = 1;
if (i > 0) {
int k = binarySearch2(d.get(i - 1).size(), d.get(i - 1), v);
c = cnt.get(i - 1).get(cnt.get(i - 1).size() - 1) - cnt.get(i - 1).get(k);
}
if (i == d.size()) {
List<Integer> dList = new ArrayList<Integer>();
dList.add(v);
d.add(dList);
List<Integer> cntList = new ArrayList<Integer>();
cntList.add(0);
cntList.add(c);
cnt.add(cntList);
} else {
d.get(i).add(v);
int cntSize = cnt.get(i).size();
cnt.get(i).add(cnt.get(i).get(cntSize - 1) + c);
}
}
int size1 = cnt.size(), size2 = cnt.get(size1 - 1).size();
return cnt.get(size1 - 1).get(size2 - 1);
}
public int binarySearch1(int n, List<List<Integer>> d, int target) {
int l = 0, r = n;
while (l < r) {
int mid = (l + r) / 2;
List<Integer> list = d.get(mid);
if (list.get(list.size() - 1) >= target) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
}
public int binarySearch2(int n, List<Integer> list, int target) {
int l = 0, r = n;
while (l < r) {
int mid = (l + r) / 2;
if (list.get(mid) < target) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
}
}
cpp 解法, 执行用时: 144 ms, 内存消耗: 13.3 MB, 提交时间: 2023-09-27 10:37:44
class Solution {
// 二分搜索
int binarySearch(int n, function<bool(int)> f) {
int l = 0, r = n;
while (l < r) {
int mid = (l + r) / 2;
if (f(mid)) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
}
public:
int findNumberOfLIS2(vector<int> &nums) {
vector<vector<int>> d, cnt;
for (int v : nums) {
int i = binarySearch(d.size(), [&](int i) { return d[i].back() >= v; });
int c = 1;
if (i > 0) {
int k = binarySearch(d[i - 1].size(), [&](int k) { return d[i - 1][k] < v; });
c = cnt[i - 1].back() - cnt[i - 1][k];
}
if (i == d.size()) {
d.push_back({v});
cnt.push_back({0, c});
} else {
d[i].push_back(v);
cnt[i].push_back(cnt[i].back() + c);
}
}
return cnt.back().back();
}
// dp
int findNumberOfLIS(vector<int> &nums) {
int n = nums.size(), maxLen = 0, ans = 0;
vector<int> dp(n), cnt(n);
for (int i = 0; i < n; ++i) {
dp[i] = 1;
cnt[i] = 1;
for (int j = 0; j < i; ++j) {
if (nums[i] > nums[j]) {
if (dp[j] + 1 > dp[i]) {
dp[i] = dp[j] + 1;
cnt[i] = cnt[j]; // 重置计数
} else if (dp[j] + 1 == dp[i]) {
cnt[i] += cnt[j];
}
}
}
if (dp[i] > maxLen) {
maxLen = dp[i];
ans = cnt[i]; // 重置计数
} else if (dp[i] == maxLen) {
ans += cnt[i];
}
}
return ans;
}
};
python3 解法, 执行用时: 80 ms, 内存消耗: 16.4 MB, 提交时间: 2023-09-27 10:35:52
# 贪心 + 前缀和 + 二分搜索
class Solution:
def findNumberOfLIS(self, nums: List[int]) -> int:
d, cnt = [], []
for v in nums:
i = bisect(len(d), lambda i: d[i][-1] >= v)
c = 1
if i > 0:
k = bisect(len(d[i - 1]), lambda k: d[i - 1][k] < v)
c = cnt[i - 1][-1] - cnt[i - 1][k]
if i == len(d):
d.append([v])
cnt.append([0, c])
else:
d[i].append(v)
cnt[i].append(cnt[i][-1] + c)
return cnt[-1][-1]
def bisect(n: int, f: Callable[[int], bool]) -> int:
l, r = 0, n
while l < r:
mid = (l + r) // 2
if f(mid):
r = mid
else:
l = mid + 1
return l
python3 解法, 执行用时: 724 ms, 内存消耗: 16.2 MB, 提交时间: 2023-09-27 10:34:29
'''
定义 dp[i] 表示以 nums[i] 结尾的最长上升子序列的长度，
cnt[i] 表示以 nums[i] 结尾的最长上升子序列的个数。
设 nums 的最长上升子序列的长度为 maxLen，
那么答案为所有满足 dp[i]=maxLen 的 i 所对应的 cnt[i] 之和。
'''
class Solution:
def findNumberOfLIS(self, nums: List[int]) -> int:
n, max_len, ans = len(nums), 0, 0
dp = [0] * n
cnt = [0] * n
for i, x in enumerate(nums):
dp[i] = 1
cnt[i] = 1
for j in range(i):
if x > nums[j]:
if dp[j] + 1 > dp[i]:
dp[i] = dp[j] + 1
cnt[i] = cnt[j] # 重置计数
elif dp[j] + 1 == dp[i]:
cnt[i] += cnt[j]
if dp[i] > max_len:
max_len = dp[i]
ans = cnt[i] # 重置计数
elif dp[i] == max_len:
ans += cnt[i]
return ans
python3 解法, 执行用时: 804 ms, 内存消耗: 16.5 MB, 提交时间: 2023-09-27 10:32:25
class Solution:
def findNumberOfLIS(self, nums: List[int]) -> int:
n = len(nums)
f = [[0, 0] for _ in range(n)]
for i in range(n):
sub_len = f[i][0]
cnt = 0
for j in range(i):
if nums[j] < nums[i]:
if f[j][0] == sub_len:
cnt += f[j][1]
elif f[j][0] > sub_len:
cnt = f[j][1]
sub_len = f[j][0]
f[i] = [sub_len + 1, cnt if cnt != 0 else 1]
max_legnth = max(f[i][0] for i in range(n))
return sum(f[i][1] for i in range(n) if f[i][0] == max_legnth)
''' 记忆化搜索
@cache
def dfs(i):
sub_len = 0
cnt = 0
for j in range(i):
if nums[j] < nums[i]:
if dfs(j)[0] == sub_len:
cnt += dfs(j)[1]
elif dfs(j)[0] > sub_len:
cnt = dfs(j)[1]
sub_len = dfs(j)[0]
return sub_len + 1, cnt if cnt != 0 else 1
max_legnth = max(dfs(i)[0] for i in range(n))
return sum(dfs(i)[1] for i in range(n) if dfs(i)[0] == max_legnth)
'''