编写程序:求一组数中的最长连续递增子序列。假设这组数以0作为结束标志。 输入: 1 9 2 5 7 3 4 6 8 0 输出: 3 4 6 8
时间: 2024-09-28 15:03:44 浏览: 30
PTA丨最长连续递增子序列
编写一个程序来找出给定整数数组中最长的连续递增子序列,可以采用动态规划的方法。这里是一个简单的Python实现:
```python
def longest_increasing_subsequence(nums):
if not nums:
return []
n = len(nums)
dp = [1] * n # 初始化每个位置的最长递增子序列长度为1
prev = [-1] * n # 存储前一个元素的索引
for i in range(1, n):
for j in range(i): # 遍历已处理过的元素
if nums[i] > nums[j]:
if dp[i] < dp[j] + 1:
dp[i] = dp[j] + 1
prev[i] = j
max_length = max(dp) # 找到最大值
result = []
current = n - 1 # 从最后一个元素开始回溯
while current != -1 and dp[current] == max_length:
result.append(nums[current])
current = prev[current]
result.reverse() # 因为初始是从右往左查找,所以结果需要反转
return result
# 示例输入
nums = [1, 9, 2, 5, 7, 3, 4, 6, 8, 0]
# 调用函数并打印结果
print(longest_increasing_subsequence(nums)) # 输出:[4, 6, 8]
```
这个程序首先初始化一个动态规划数组`dp`和一个记录前一个元素索引的数组`prev`,然后遍历数组,更新这两个数组。最后,从`prev`数组中回溯构建最长递增子序列。
阅读全文