当前位置： 面试刷题>> 最长升序子序列的个数 (经典算法题500道)
### 题目描述
给定一个整数数组 `nums`，你需要找到其中最长升序子序列（LIS, Longest Increasing Subsequence）的长度以及具有这个长度的升序子序列的个数。
**注意**：数组中的元素可能不是唯一的，且最长升序子序列的长度可能不止一个。
**示例 1**:
```
输入: nums = [1,3,5,4,7]
输出: 长度: 3, 个数: 2
解释: 两个最长升序子序列是 [1, 3, 5] 和 [1, 3, 7]。
```
**示例 2**:
```
输入: nums = [2,2,2,2,2]
输出: 长度: 1, 个数: 5
解释: 最长升序子序列的长度是 1，并且存在 5 个这样的子序列，即 [2], [2], [2], [2], [2]。
```
### 解题思路
这个问题可以通过动态规划解决。我们需要两个数组：
1. `lengths`：记录到当前位置为止，以当前元素结尾的最长升序子序列的长度。
2. `counts`：记录到当前位置为止，以当前元素结尾且长度为 `lengths[i]` 的最长升序子序列的个数。
另外，我们还需要一个辅助数组 `prev` 来记录每个元素的前一个元素索引，以便在统计个数时回溯。
### PHP 代码示例
```php
function findNumberOfLIS($nums) {
$n = count($nums);
if ($n <= 1) {
return [$n, 1];
}
$lengths = array_fill(0, $n, 1);
$counts = array_fill(0, $n, 1);
$prev = array_fill(0, $n, -1);
$maxLength = 1;
$totalCounts = 0;
for ($i = 1; $i < $n; $i++) {
for ($j = 0; $j < $i; $j++) {
if ($nums[$i] > $nums[$j]) {
if ($lengths[$j] + 1 > $lengths[$i]) {
$lengths[$i] = $lengths[$j] + 1;
$counts[$i] = $counts[$j];
$prev[$i] = $j;
} elseif ($lengths[$j] + 1 == $lengths[$i]) {
$counts[$i] += $counts[$j];
if ($prev[$i] == -1) {
$prev[$i] = $j;
}
}
}
}
if ($lengths[$i] > $maxLength) {
$maxLength = $lengths[$i];
$totalCounts = $counts[$i];
} elseif ($lengths[$i] == $maxLength) {
$totalCounts += $counts[$i];
}
}
return [$maxLength, $totalCounts];
}
// 测试
$nums = [1, 3, 5, 4, 7];
$result = findNumberOfLIS($nums);
echo "长度: " . $result[0] . ", 个数: " . $result[1];
```
### Python 代码示例
```python
def findNumberOfLIS(nums):
n = len(nums)
if n <= 1:
return [n, 1]
lengths = [1] * n
counts = [1] * n
prev = [-1] * n
maxLength = 1
totalCounts = 0
for i in range(1, n):
for j in range(i):
if nums[i] > nums[j]:
if lengths[j] + 1 > lengths[i]:
lengths[i] = lengths[j] + 1
counts[i] = counts[j]
prev[i] = j
elif lengths[j] + 1 == lengths[i]:
counts[i] += counts[j]
if lengths[i] > maxLength:
maxLength = lengths[i]
totalCounts = counts[i]
elif lengths[i] == maxLength:
totalCounts += counts[i]
return [maxLength, totalCounts]
# 测试
nums = [1, 3, 5, 4, 7]
result = findNumberOfLIS(nums)
print("长度:", result[0], "个数:", result[1])
```
### JavaScript 代码示例
```javascript
function findNumberOfLIS(nums) {
const n = nums.length;
if (n <= 1) {
return [n, 1];
}
const lengths = new Array(n).fill(1);
const counts = new Array(n).fill(1);
const prev = new Array(n).fill(-1);
let maxLength = 1;
let totalCounts = 0;
for (let i = 1; i < n; i++) {
for (let j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
if (lengths[j] + 1 > lengths[i]) {
lengths[i] = lengths[j] + 1;
counts[i] = counts[j];
prev[i] = j;
} else if (lengths[j] + 1 === lengths[i]) {
counts[i] += counts[j];
}
}
}
if (lengths[i] > maxLength) {
maxLength = lengths[i];
totalCounts = counts[i];
} else if (lengths[i] === maxLength) {
totalCounts += counts[i];
}
}
return [maxLength, totalCounts];
}
// 测试
const nums = [1, 3, 5, 4, 7];
const result = findNumberOfLIS(nums);
console.log(`长度: ${result[0]}, 个数: ${result[1]}`);
```
**码小课网站中有更多相关内容分享给大家学习**，希望以上内容对你有所帮助！