当前位置： 面试刷题>> 升序子序列 (经典算法题500道)
### 题目描述补充
**题目：升序子序列**
给定一个整数数组 `nums`，你的任务是找出数组中所有可能的**严格递增子序列**的长度，并以列表（或数组）形式返回这些长度，不需要返回具体的子序列本身。
**注意**：
- 数组中的元素可能不唯一。
- 递增子序列是指子序列中的元素从左到右依次增大，但不必连续。
**示例**：
输入：`nums = [4, 6, 7, 7]`
输出：`[1, 2, 3, 4]`
解释：可能的递增子序列有 `[4], [6], [7], [4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7]`，对应长度分别为 1, 1, 1, 2, 2, 3, 4。
### PHP 示例代码
```php
function lengthOfLIS($nums) {
$n = count($nums);
$dp = array_fill(0, $n, 1); // 初始化dp数组，每个元素至少为1（自身为子序列）
$maxLength = 1;
for ($i = 1; $i < $n; $i++) {
for ($j = 0; $j < $i; $j++) {
if ($nums[$i] > $nums[$j]) {
$dp[$i] = max($dp[$i], $dp[$j] + 1);
}
}
$maxLength = max($maxLength, $dp[$i]);
}
// 生成所有可能的长度
$result = [];
for ($len = 1; $len <= $maxLength; $len++) {
$result[] = $len;
}
return $result;
}
// 示例用法
$nums = [4, 6, 7, 7];
$result = lengthOfLIS($nums);
print_r($result);
```
### Python 示例代码
```python
def lengthOfLIS(nums):
n = len(nums)
dp = [1] * n # 初始化dp数组，每个元素至少为1
maxLength = 1
for i in range(1, n):
for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j] + 1)
maxLength = max(maxLength, dp[i])
# 生成所有可能的长度
return list(range(1, maxLength + 1))
# 示例用法
nums = [4, 6, 7, 7]
result = lengthOfLIS(nums)
print(result)
```
### JavaScript 示例代码
```javascript
function lengthOfLIS(nums) {
const n = nums.length;
const dp = new Array(n).fill(1); // 初始化dp数组
let maxLength = 1;
for (let i = 1; i < n; i++) {
for (let j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
maxLength = Math.max(maxLength, dp[i]);
}
// 生成所有可能的长度
const result = [];
for (let len = 1; len <= maxLength; len++) {
result.push(len);
}
return result;
}
// 示例用法
const nums = [4, 6, 7, 7];
const result = lengthOfLIS(nums);
console.log(result);
```
**码小课**网站中有更多关于算法和数据结构的相关内容分享给大家学习，欢迎访问以获取更多知识和实践机会。